java - 计算字符串出现次数和比较次数 (KMP)

Question

我正在尝试使用搜索算法KMP来计算模式出现次数和所需比较(在下面的代码中称为匹配)。

我尝试执行以下操作:

public class KMP {

    private String pat;
    private int[][] dfa;
    private static int match;
    private static int count;

    public KMP(String pat) {
        // Build DFA from pattern.      
        this.pat = pat;
        int M = pat.length();
        int R = 256;
        dfa = new int[R][M];
        dfa[pat.charAt(0)][0] = 1;
        for (int X = 0, j = 1; j < M; j++) {
            // Compute dfa[][j].         
            for (int c = 0; c < R; c++) {
                dfa[c][j] = dfa[c][X];           // Copy mismatch cases.        
                dfa[pat.charAt(j)][j] = j + 1;   // Set match case.    
                X = dfa[pat.charAt(j)][X];       // Update restart state.   
            }
        }
    }

    public int search(String txt) {
        // Simulate operation of DFA on txt.    
        int i, j, N = txt.length(), M = pat.length();
        for (i = 0, j = 0; i < N && j < M; i++) {
            j = dfa[txt.charAt(i)][j];
        }
        if (j == M) {
            return i - M; // found (hit end of pattern)  
        } else {
            return N;     // not found (hit end of text)  
        }
    }

    public static void main(String[] args) {

        String pat = "babba";
        String txt = "aaaaaaaaaaaabbaaababbaaaaababbaaaa";
        int lastIndex = 0;

        KMP kmp = new KMP(pat);
        int offset = kmp.search(txt);

        System.out.println("text:    " + txt);
        System.out.print("pattern: ");

        while (lastIndex != txt.length()) {
            for (int i = 0; i < offset; i++) {
                lastIndex++;
                match++;
            }
            count++;
        }

        System.out.println(pat);
        System.out.println("count:   " + count);
        System.out.println("match:   " + match);
    }
}

我的代码在像这样编译时工作得很好，但是当我将String txt属性更改为aaaaaaaaaaaaabbaaababbaaaaababbaaaababba之类的东西时，它给了我一个意想不到的负计数值(另外，实际运行代码大约需要 30 秒)。

我正在尝试找到一种更好的解决方案来计算出现次数，并且我还想知道我的代码出了什么问题，因为它只在某些情况下有效。

Answer 1

原因是你的循环条件。

while (lastIndex != txt.length())

您的问题字符串的长度为 38，偏移量为 17。
每个 for 循环 lastIndex 都会增加 17。
在第三个 for 循环之后，它的值为 51。
满足条件并且循环继续。
它仅在可能几次 int 溢出后结束，从而导致负计数值。

而且你也无法计算这样的发生次数。
kmp.search() 仅返回模式第一次出现的开始位置。
例如

String txt = "aaaaaaaaaaaaaaaaababbaaaaaaaaaaaaa";

您的代码返回count = 2。

解决方案是在每次搜索后分割字符串，然后搜索模式后面的子字符串。

KMP kmp = new KMP(pat);
int offset = kmp.search(txt);
while (offset != txt.length()) {
    count++;
    txt = txt.substring(offset+pat.length());
    offset = kmp.search(txt);
}
System.out.println("count:   " + count);

编辑:上面的代码仅适用于非重叠模式。

txt = txt.substring(offset+at.length());

需要改为

txt = txt.substring(offset+1);

是否有重叠。