题目描述

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

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

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

样例

输入

3
aba
5
ababa

输出

0 2

理解图片

C++ 代码

#include<iostream>
using namespace std;
const int N = 1e5 + 10;

int nex[N];
char p[N],s[N*10];

int n,m;

int main()
{
    scanf("%d%s%d%s",&n,p+1,&m,s+1);
    //求next数组next[j]表示以j结尾的字符串的最长公共前后缀
    for(int i = 2,j = 0;i <= n;i++)
    {
        while(j && p[i] != p[j+1]) j = nex[j];
        if(p[i] == p[j+1]) j++;
        nex[i] = j;
    }

    //kmp匹配过程
    for(int i = 1,j = 0;i <= m;i++)
    {
        while(j && s[i] != p[j+1]) j = nex[j];
        if(s[i] == p[j+1])
        {
            j++;
            if(j == n)
           {
             printf("%d ",i - n);
             j = nex[j];
           }
        }
    } 
    puts("");
    return 0;
}