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」のシーケンスに一致する多くの可能性があるようなものは、壊滅的なバックトラッキングにつながります。

これはこれらの 2 文字の任意のシーケンスに一致するため、文字クラスに置き換える方がよいでしょう[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 に答える