java - KMP 字符串匹配算法陷入循环

Question

我正在尝试使用 CLRS 实现 KMP 字符串匹配算法，但是文本输入为“bbaa”，模式输入为“aab”，它陷入了 while 的无限循环在 getKMPPrefix 函数中循环。我的代码如下:

private int[] getKMPPrefix(char[] p, int m) {
    int[] prefix = new int[m];
    prefix[0] = 0;
    int k = 0;
    for(int q = 1; q < m; q++) {
        while(k > 0 && p[k] != p[q] ) { //Stuck here
            k = prefix[k];
        }
        if(p[k] == p[q]) {
            k++;
        }
        prefix[q] = k;
    }
    return prefix;
}

public void kmp(String text, String pattern) {
    char[] t = text.toCharArray();
    char[] p = pattern.toCharArray();
    int n = text.length();
    int m = pattern.length();

    int[] prefix = getKMPPrefix(p, m);

    int q = 0;
    for(int i = 1; i < n; i++) {
        while(q > 0 && p[q] != t[i]) {
            q = prefix[q];
        }
        if(p[q] == t[i]) {
            q++;
        }
        if(q == m) {
            System.out.println("Pattern occurs with shift " + (i-m+1));
            q = prefix[m-1];
        }
    }
}

知道为什么会这样吗？

Answer 1

这是正在发生的事情:

它到达了行:

while(k > 0 && p[k] != p[q] ) { //Stuck here

k=0 显然这会失败，它会跳出循环并转到下一个

if(p[k] == p[q]) {
            k++;
        }

在你的例子中，输入是 aab 所以这是真的 p[0]=p[1]=a

现在，k=1

现在您将 k 的值分配给 prefix

prefix[q] = k;

现在它陷入了僵局。

现在会回到while循环

 while(k > 0 && p[k] != p[q] ) { //Stuck here
            k = prefix[k];
        }

注意，您刚刚在前面的循环中赋值 prefix[q] = k; 即 p[1] = 1

当谈到 while 循环 k=1 和 'p[1] != p[2]' 即 a!=b 它通过并进入循环

k = prefix[k];

k=1 和 prefix[1] = 1，这意味着您正在将值 1 重新分配给 k

它再次回到 while 循环和 k=1 和 p=1 的值，因为它从未经过 while 循环到递增 p

存在死锁，对于 while 循环，条件将保持为 true，并且程序永远不会退出 while 循环。

您可以更改 while 循环条件或在 while 循环内增加 p 或在特定条件后在 while 内增加 break。我解释了 Deadlock，尽管尝试自己找出程序。祝你好运