algorithm - KMP 计数字符串出现次数

Question

我已经实现了用于在字符串 B 中搜索字符串 A 的 Knuth-Morris-Pratt 算法。如果找到字符串，则返回字符串的第一个位置，否则返回 -1。但是现在我想统计字符串 A 在字符串 B 中的总出现次数。

我已经尝试了一种简单的方法并且它正在工作，但这似乎并不有效，因为它需要花费很多时间处理大字符串。

谁能帮我解决这个问题？我想要一种更高效的 KMP 方法。

这是我的测试。

public static int searchStringWithKnuthMorrisPratt(String s, String t)
    {
    int m=s.length();
    int n=t.length();
    int i=0,j=0,
            k=0
                    ;
    int[] B=new int[m+1];
    B[0]=-1; B[1]=0;
    for (int l=2; l<=m; l++)
    {
    while ((k>=0) && !(s.charAt(k)==s.charAt(l-1))) k=B[k];
    B[l]=++k;
    }
    while (i<=(n-m))
    {
    while ((j<m) && (s.charAt(j)==t.charAt(i+j))) j++;
    if (j==m) return(i);
    i=i+j-B[j];
    j=Math.max(0, B[j]);
}
    return(-1);
}

public static void main(String[] args)
{
            String stringA = "ST";
            String stringB = "XSTXXXSTX";
            int count = 0;
            int result = searchStringWithKnuthMorrisPratt(stringA,stringB);
            while(result>-1) {
            count++
            stringB = stringB.substring(result+2);
            result= searchStringWithKnuthMorrisPratt(stringA,stringB);

              }
}

//编辑:我解决了我的问题我只需要正确阅读维基百科文章。

Answer 1

您提到“处理大字符串需要很多时间”。

我建议您使用 Boyer Moore Horspool 算法。随着模式长度的增加，它变得更快。此外，使用子字符串剪切输入文本会降低性能。相反，您可以添加一个参数来指定搜索的起点。