字符串中子字符串出現的性能

我遇到了查找另一個字符串中所有子字符串出現的任務，並想知道什麼是解決此問題的最佳算法。字符串中子字符串出現的性能

爲了演示目的，我使用了字符串「貓坐在墊子上」並搜索子字符串「at」的所有出現。這將最終導致3的occurence計數由於我在Java的時刻，突然出現在我的腦海裏的第一件事編程是這樣的：

public static void main(String[] args) { 

     int count=0; 
     String s = "The cat sat on the mat"; 

     Pattern pattern = Pattern.compile("at"); 
     Matcher matcher = pattern.matcher(s); 
     while(matcher.find()){ 
      count++; 
     } 

     System.out.println("Pattern: "+pattern+" Count: "+count); 
    }

不知怎的，我懷疑，這是最佳的解決方案爲這個問題。所以，如果有人知道最佳（或至少相當不錯）的解決方案應該看起來...請回答！你可以用任何語言發佈你的答案，不一定是java（儘管那會很棒:)）。

非常感謝！

來源

2010-08-27 evermean

在某種程度上取決於搜索字符串的長度與搜索字符串的長度，字母大小以及您要執行的搜索次數。 – 2010-08-27 09:49:27

但是如果你還沒有測量過性能問題，請不要擔心...... – 2010-08-27 09:49:52

有很多令人印象深刻的子串算法。經常提到Boyer-Moore算法（http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm），但還有其他替代方法，如http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm和http://en.wikipedia.org/wiki/Rabin-karp。

來源

2010-08-27 10:02:42 Patrick

Boyer-Moore +1。順便說一句，互聯網上有一些關於BM的謠言（Reddit也許）關於BM，找不到鏈接。但谷歌爲它，你應該看到一些關於它的動畫討論。很有用。 – Mikos 2010-08-27 12:04:06

像往常一樣，這取決於。

理論上最好的方法是可能使用後綴樹 - 但它們只對非常大的字符串開始有意義。後綴數組稍微難於使用，但對較小的字符串有意義。 IIRC，zlib deflate算法使用後綴數組來查找重複的子串。無論哪種情況，算法都不是直截了當的，需要相當多的研究纔能有效地理解和實施。

如果你只是擔心程序員的生產力和易於理解的代碼，我想很難打敗你寫的東西。假設一個合理的智能正則表達式解析器，它可能足夠快，正常使用。

來源

2010-08-27 09:57:28 Hari

沒有正則表達式的開銷：

public static void main(String[] args) { 

    int count = 0; 
    String s = "The cat sat on the mat"; 
    String substring = "at"; 

    int pos = s.indexOf(substring); 
    while (pos > -1) { 
     count++; 
     pos = s.indexOf(substring, pos + 1); 
    } 

    System.out.println("Pattern: "+pattern+" Count: "+count); 
}

我做了一個快速測試搜索「在」在維基百科上的Boyer–Moore string search algorithm文章的文本。他們都找到了相同數量的匹配，但是在我的機器上執行這個10.000次採用正則表達式算法1702毫秒，這只是192！

來源

2010-08-28 15:37:33 Kwebble

嘿，太好了！非常感謝！ – evermean 2010-08-29 09:36:26

字符串中子字符串出現的性能

回答

相關問題