algorithm - 子字符串在字符串中出现的性能

Question

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

出于演示目的，我使用了字符串“The cat sat on the mat”并搜索所有出现的子字符串“at”。这最终应该导致出现次数为 3。因为我现在正在用 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(尽管那会很棒 :))。

非常感谢!

Answer 1

有很多令人印象深刻的子串算法。通常提到 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 .