How to reduce runtime when using regex?

Question

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);  
    }
}

Looks like you need to use basic String manipulation here. — Luiggi Mendoza
– Luiggi Mendoza, Commented Mar 31, 2013 at 16:56

stema · Accepted Answer · 2013-03-31 18:33:22Z

2

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.

answered Mar 31, 2013 at 18:33

stema

93.5k20 gold badges110 silver badges138 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

dshgna Over a year ago

It indeed does and passed the test! Its a really valuable technique. Thank you!

Sergiu Toarca · Accepted Answer · 2013-04-02 16:25:57Z

0

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.

answered Apr 2, 2013 at 16:25

Sergiu Toarca

2,78921 silver badges24 bronze badges

Collectives™ on Stack Overflow

How to reduce runtime when using regex?

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related