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

我遇到了查找另一个字符串中所有子字符串出现的任务，并想知道什么是解决此问题的最佳算法。字符串中子字符串出现的性能

为了演示目的，我使用了字符串“猫坐在垫子上”并搜索子字符串“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

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

回答

相关问题