KMP前缀表

Question

我正在阅读有关KMP字符串匹配的内容.
它需要通过构建前缀表来预处理模式.
例如,对于字符串ababaca,前缀表是: P = [0, 0, 1, 2, 3, 0, 1]
但我不清楚数字显示的是什么.我读到它有助于在模式转换时找到模式的匹配但我无法将此信息与表中的数字相关联.

Answer 1

每个数字都属于相应的前缀("a","ab","aba",...),并且对于每个前缀,它表示与该前缀匹配的该字符串的最长后缀的长度.我们在这里不将整个字符串计为后缀或前缀,它被称为自我后缀和自我前缀(至少在俄语中,不确定英语术语).

所以我们有字符串"ababaca".我们来看看吧.KMP为每个非空前缀计算前缀函数.让我们定义s[i]为字符串,p[i]作为前缀函数.前缀和后缀可能重叠.

+---+----------+-------+------------------------+
| i |  s[0:i]  | p[i]  | Matching Prefix/Suffix |
+---+----------+-------+------------------------+
| 0 | a        |     0 |                        |
| 1 | ab       |     0 |                        |
| 2 | aba      |     1 | a                      |
| 3 | abab     |     2 | ab                     |
| 4 | ababa    |     3 | aba                    |
| 5 | ababac   |     0 |                        |
| 6 | ababaca  |     1 | a                      |
|   |          |       |                        |
+---+----------+-------+------------------------+

计算字符串S的前缀函数的简单C++代码:

vector<int> prefixFunction(string s) {
    vector<int> p(s.size());
    int j = 0;
    for (int i = 1; i < (int)s.size(); i++) {
        while (j > 0 && s[j] != s[i])
            j = p[j-1];

        if (s[j] == s[i])
            j++;
        p[i] = j;
    }   
    return p;
}

Answer 2

这段代码可能不是最短的，但很容易理解的代码流。用于计算前缀数组的简单 Java 代码

    String pattern = "ababaca";
    int i = 1, j = 0;
    int[] prefixArray = new int[pattern.length];
    while (i < pattern.length) {

        while (pattern.charAt(i) != pattern.charAt(j) && j > 0) {
            j = prefixArray[j - 1];

        }
        if (pattern.charAt(i) == pattern.charAt(j)) {
            prefixArray[i] = j + 1;
            i++;
            j++;

        } else {
            prefixArray[i] = j;
            i++;
        }
    }

    for (int k = 0; k < prefixArray.length; ++k) {
        System.out.println(prefixArray[k]);
    }

它产生所需的输出 -

0 0 1 2 3 0 1