CODEWITHSUNDEEP
javaregex
dshgna
dshgna

Reputation: 842

How to reduce runtime when using regex?

I've been using regex to solve the "Broken Necklace" problem at USACO. While it works fine for smaller inputs, albeit a very complicated regex expression, it exceeds the given time limit for larger inputs.

For further input, here is the code I used. My question is on how I could improve the runtime while still using regex.

All help is greatly appreciated. I'm a total newbie to competitive programming and am really stuck: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);  
    }
}

Upvotes: 2

Views: 309

Answers (2)

Sergiu Toarca
Sergiu Toarca

Reputation: 2749

There is a much simpler regular expression than the ones given so far

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

You can see a really nice visualization of your algorithm on debuggex. Slide the black triangle along the test string and keep your eye on the group 1 match. This is what your algorithm is looking at to determine the length. Note that the example string has already been concatenated to itself so that the endpoints work.

Upvotes: 0

stema
stema

Reputation: 92976

Stuff like (b*w*)* does have many possibilities to match a sequence of "b" and "w" this will lead to catastrophic backtracking.

Because this will match any sequence of those two letters it would be better to replace it with a character class [bw]*.

So your expression would look something like this:

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

This expression should match a lot quicker.

Upvotes: 2

Related Questions