如何在使用正則表達式時減少運行時間？

我一直在使用正則表達式解決USACO處的「Broken Necklace」問題。雖然它對於較小的輸入工作正常，儘管它是一個非常複雜的正則表達式，但它對於較大的輸入超出了給定的時間限制。如何在使用正則表達式時減少運行時間？

有關更多信息，請參閱我使用的代碼。我的問題是如何在仍然使用正則表達式的同時改進運行時。

非常感謝所有幫助。我是一個競爭性編程的新手，我真的陷入了困境：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); 
    } 
}

來源

2013-03-31 dshgna

看起來你需要在這裏使用基本的'字符串'操作。 –

東西一樣(b*w*)*確實有很多的可能性，以配合「B」的序列和「W」這將導致catastrophic backtracking。

因爲這將匹配這兩個字母的任何序列，所以最好用字符類[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-31 18:33:22 stema

它確實通過了測試！它是一種非常有價值的技術謝謝！ – dshgna

還有一個更簡單的正則表達式比迄今

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

你可以看到debuggex你的算法的一個非常好的可視化給出的那些。沿測試線滑動黑色三角形，並注意組1比賽。這就是你的算法正在研究的長度。請注意，示例字符串已經連接到自身，以便端點工作。

來源

2013-04-02 16:25:57

如何在使用正則表達式時減少運行時間？

回答

相關問題