KMP前缀表

  • Z时代
  • 2024-01-10
  • 分类：问答

我正在阅读有关KMP字符串匹配的内容。

它需要通过构建前缀表来对模式进行预处理。

例如，对于字符串ababaca，前缀表为： P = [0, 0, 1, 2, 3, 0, 1]

但是我不清楚数字显示了什么。我读到它在移位时有助于找到模式的匹配项，但无法将此信息与表格中的数字连接。

回答：

每个数字都属于相应的前缀（“ a”，“ ab”，“

aba”，…），对于每个前缀，它表示此字符串中与前缀匹配的最长后缀的长度。在此，我们不将整个字符串算作后缀或前缀，这称为自后缀和自前缀（至少在俄语中，不确定英语术语）。

因此，我们有字符串“ ababaca”。让我们看看。KMP为每个非空前缀计算Prefix

Function。让我们定义s[i]为字符串，p[i]作为Prefix函数。前缀和后缀可能重叠。

+---+----------+-------+------------------------+
| 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的Prefix函数的简单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;
}

以上是 KMP前缀表 的全部内容， 来源链接： utcz.com/qa/427520.html

回到顶部