#L E S S O N# K.M.P. 算法

Zeneks · 2023-10-23 21:10:49 · 个人记录

Knuth-Morris-Pratt Algorithm

定义

K.M.P. 算法是一种模式字符串匹配算法。

给定一个文本串和一个模式串，查询模式串在文本串中出现的次数或位置等一类问题称为模式串匹配问题。

为便于表述，预先规定以下几个量

• s：文本串，长度为 n

• t：模式串，长度为 m

• nxt[M]：部分匹配表（partial match table），表示以第 i 个字符为结尾的长度为 j 的子串与从第 1 个字符开始的长度为 j 的字串相等

  ​ 例如 T 为 ababaca，其对应的nxt数组如下表所示：

  i	1	2	3	4	5	6	7
  nxt [i]	0	0	1	2	3	0	1

实现

输入格式

第一行为一个字符串，即为s1。 第二行为一个字符串，即为s2​。

输出格式

首先输出若干行，每行一个整数，按从小到大的顺序输出s2在s1中出现的位置。 最后一行输出 ∣s2∣个整数，第 i 个整数表示 s2的长度为 i的前缀的最长 border 长度。

#include <iostream>
#include <cstring>
using namespace std;
char s[1145141], t[114514];
int nxt[1145141], n, m;
int main (void)
{
    cin >> s+1 >> t+1;
    m = strlen (t+1);
    n = strlen (s+1);
    for (int i=2, k=0;i<=m;i++) {
        while (k && t[k+1] != t[i])
            k = nxt[k];
       if (t[i] == t[k+1])
           k ++;
        nxt[i] = k;
    }
    for (int i=1, k=0;i<=n;i++) {
        while (k && t[k+1] != s[i])
            k = nxt [k];
        if (t[k+1] == s[i]) k ++;
        if (k == m) {
            cout << i - m +1 << endl;
            k = nxt[k];
        }
    }
    for (int i=1;i<=m;i++)
        cout << nxt [i] << ' ';
    return 0;
}