1. 例题

给定一个模式串 S，以及一个模板串 P，所有字符串中只包含大小写英文字母以及阿拉伯数字。模板串 P 在模式串 S 中多次作为子串出现，求出模板串 P 在模式串 S 中所有出现的位置的起始下标。

2. next 数组

在 KMP 算法中，通常使字符串首字符位于下标为 1 的位置。如，对于模板串 P ：“abcdabd”，有

index 0 1 2 3 4 5 6 7
P a b c d a b d
nxt 0 0 0 0 0 1 2 0

其中，next 数组初始可使 nxt[0] 和 nxt[1] 均为 0，后续值可采用如下算法计算：

char p[n+2]{}; 		// scanf("%s", p+1); or cin >> p+1;
int nxt[n+1]{};

void calNext() {
    for (int i = 2, j = 0; i <= n; ++i) {
        while (j && p[i] != p[j+1]) {
            j = nxt[j];
        }
        if (p[i] == p[j+1]) {
            ++j;
        }
        nxt[i] = j;
	}
}

3. 模式串匹配

char s[m+2]{};		// scanf("%s", s+1); or cin >> s+1;

void find() {
    for (int i = 1, j = 0; i <= m; ++i) {
        while (j && s[i] != p[j+1]) {
            j = nxt[j];
        }
        if (s[i] == p[j+1]) {
            ++j;
        }
        if (j == n) {
            // The pattern string has been found!
            cout << i - n << endl;
            j = nxt[j];
        }
    }
}