题目

KMP字符串 经典问题

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

输入格式

第一行输入整数 N，表示字符串 P 的长度。
第二行输入字符串 P。
第三行输入整数 M，表示字符串 S 的长度。
第四行输入字符串 S。

输出格式

共一行，输出所有出现位置的起始下标（下标从 0 开始计数），整数之间用空格隔开。

数据范围

1≤N≤1e5
1≤M≤1e6

kmp主要在于理解next数组 整体上kmp过程与next求解过程相似 理解j的移动过程

代码

#include <iostream>
using namespace std;

const int N = 100010,M = 1000010;

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

int main()
{
    cin >> n >> p + 1 >> m >> s + 1;
    //ne数组求解 ###针对模板字符串自身（p数组）### 进行位置匹配
    //从第二个数和第一个数字开始匹配
    //匹配成功就j++ 然后赋给ne数组
    //匹配失败就利用j = ne[j]将j向前回滚
    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;
    }
    //kmp匹配 
    //遍历待匹配字符串全部
    for(int i = 1, j = 0; i <= m; i++)
    {
        //匹配失败就将j移动到最大前后缀的位置上 继续匹配
        while(j && s[i] != p[j+1]) j = ne[j];
        //匹配成功就推进 j++
        if(s[i] == p[j+1]) j++;
        //如果此时j和模板字符串长度相同说明匹配成功
        if(j == n) 
        {
            //输出i-n 即待匹配字符串中成功匹配的开始位置
            printf("%d ", i - n); 
            //j移动到最大前后缀的位置，若i没遍历完可能存在多组解
            j = ne[j];      
        }
    }

    return 0;
}