How to reduce runtime when using regex?

[abraptirl]

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!\[code\]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); }}\[/code\]