题目描述

给定一个模式串S，以及一个模板串P，所有字符串中只包含大小写英文字母以及阿拉伯数字。

模板串P在模式串S中多次作为子串出现。

求出模板串P在模式串S中所有出现的位置的起始下标。

样例

3
aba
5
ababa

0 2

算法

(KMP字符串)

1. 首先明确一下数组ne[j]的含义，在比较s串和p串的时候，当s[i]和p[j + 1]不同的时候，这时候s[i - 1]和p[j]也是处于同一位置的，重点是二者相同。ne[j]就是从j点向前看，得到的一个子区间中的字符串，和从p串的首字符开始向后看，长度相等，字符相同的最大长度。因此我们更新j，永远是j = ne[j]。
2. 如何计算ne[]数组呢，同时对2个p串进行KMP算法的流程，重点是，主串的下标是从2开始的，因为输入的时候，下标是从1开始的，但是ne[1]是等于0，因为在求ne[]数组的for()中，ne[i]对应的是j + 1，ne[1]对应的是p[0 + 1]，这时候模式串没有字符，所以ne[1] = 0，也就是最长公共前缀和后缀长度为0.
3. 2个for()循环的算法流程很像，j等于0的时候，是没有ne[j]的，接下来要先判断if(s[i] == p[j + 1])，如果满足，j ++。如果先判断if(j == 0)，j就永远是0，就永远在continue，那么最后就没有输出。
4. 最后的起始位置是i - n，不懂的自己推一下。

时间复杂度

$O(n + m)$

参考文献

C++ 代码

#include <iostream>

using namespace std;

const int N = 100010, M = 1000010;

int n, m;
char s[M], p[N];
int ne[N];

int main()
{
    scanf("%d%s%d%s", &n, p + 1, &m, s + 1);        // **1

    for(int i = 2, j = 0; i <= n; i ++)
    {
        ne[1] = 0;                                  // **2
        while(j && p[i] != p[j + 1]) j = ne[j];     // **3

        if(p[i] == p[j + 1]) j ++;                  // **4
        if(j == 0) continue;                        // **5

        ne[i] = j;                                  // **6
    }

    for(int i = 1, j = 0; i <= m; i ++)
    {
        while(j && s[i] != p[j + 1]) j = ne[j];

        if(s[i] == p[j + 1]) j ++;
        if(j == 0) continue;

        if(j == n)
        {
            printf("%d ", i - n);                   // **7
            j = ne[j];                              // **8
        }
    }

    return 0;
}