题目描述

一个较短的字符串是一个较长的字符串的子串,不一定只出现过一次,输出这个子串在长串中的所有起始下标位置

背模板需要理清的思路

核心就是暴力时在每个i上都比较m次，而kmp是在每个i上通过ne[j]使比较的次数减少。

注意是j == m(模式串的长度)，真的有被自己蠢哭！！！！

①ne[N]意思是p数组的当前观察前N个元素,得到这前N个元素的前缀与后缀相同的时候最大的前缀元素个数.
③j = ne[j]的意思是j要往前跳,跳到上一次的最大前后缀相等的元素个数
③两个for循环分别有不同的含义
第一个for循环是为了找到子串p的最大前后缀的元素个数.
第二个是将子串与原数组进行匹配,先让子串与原串对齐并匹配到第一个不相同的元素的地方,先按子串遍历,再按原

代码写法上的特点

①输入时cin >> s + 1代表从下标为1的位置开始输入
②i - n的意思是子串已经匹配完毕,此时因为存入的数组是下标1开始,但我们需要将数组视为从0开始,所以不用i - n + 1.

参考文献

参考y总的代码

C++ 代码

#include <iostream>

using  namespace std;

const int N = 1e5 + 10, M = 1e6 + 10;
int n, m;
char s[N], p[M];
int ne[N];

int main()
{


    cin >> n >> p + 1 >> m >> s + 1;

    for (int i = 2, j = 0; i <= n; i ++ )
    {

        while (j && p[i] != p[j + 1]) j = ne[j];
        if (p[i] == p[j + 1]) j ++;
        ne[i] = j;



    }


    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 == n) 
        {
            printf("%d ", i - n );
            j = ne[j];

        }
    }

    return 0;
}