2

我一直在使用正则表达式来解决USACO的“断项链”问题。虽然它适用于较小的输入，尽管它是一个非常复杂的正则表达式，但它超过了较大输入的给定时间限制。

如需进一步输入，这是我使用的代码。我的问题是如何在仍然使用正则表达式的同时改进运行时。

非常感谢所有帮助。我是竞争性编程的新手，我真的被困住了：s！

class beads {

    public static void main(String[] args) throws IOException{
        BufferedReader f = new BufferedReader(new FileReader("beads.in"));
        //BufferedReader f = new BufferedReader(new FileReader("beads.txt"));
        PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("beads.out")));

        int numBeads=Integer.parseInt(f.readLine());
        String input=f.readLine();
        String beadSequence=input.concat(input);

        Pattern p1=Pattern.compile("^(w*r*)|^(w*b*)*");
        Matcher m1=p1.matcher(input);


        while(m1.find()){
            String k=m1.group();
            //System.out.println(k);
            if(k.length()==numBeads){
                out.println(k.length());
                out.close();
                System.exit(0);
            }
        }


        //System.out.println(input);
        //System.out.println(beadSequence);
        Pattern p=Pattern.compile("(?=((b*w*)*b+w*r+(w*r*)*|(r*w*)*r+w*b+(w*b*)*))(^|(?<=w)b|(?<=b)w|(?<=w)r|(?<=r)w)");

        Matcher m=p.matcher(beadSequence);


        List<String> solutions=new ArrayList<String>();
        int length=0;

        while(m.find()){

            String k=m.group(1);
            //System.out.println(m.group(1));
            if (k.length()>length)length=k.length();
        }


       out.println(length);

        out.close();                                 
        System.exit(0);  
    }
}
4

2 回答 2

2

类似的东西(b*w*)*确实有很多可能性来匹配“b”和“w”的序列，这将导致灾难性的回溯。

因为这将匹配这两个字母的任何序列，所以最好用字符类替换它[bw]*。

所以你的表达看起来像这样：

Pattern p=Pattern.compile("(?=([bw]*b+w*r+[rw]*|[rw]*r+w*b+[bw]*))(^|(?<=w)b|(?<=b)w|(?<=w)r|(?<=r)w)");

这个表达式应该匹配得更快。

于 2013-03-31T18:33:22.063 回答
0

有一个比目前给出的更简单的正则表达式

(?=([bw]*b+[rw]*|[rw]*r+[bw]*)).

你可以在debuggex上看到你的算法的一个非常好的可视化。沿着测试线滑动黑色三角形，并密切关注第 1 组比赛。这就是您的算法正在查看以确定长度的内容。请注意，示例字符串已经连接到自身，以便端点工作。

于 2013-04-02T16:25:57.063 回答