题目描述

推荐 KMP解析
https://www.acwing.com/solution/content/14666/

模板

#include <iostream>

using namespace std;

//模板串和模式串的下标都从1开始
//next数组的下标也从1开始，且next[1]对应的前缀和后缀都是空集，故next[1]=0
const int N = 1000010, M = 100010;
int ne[M];//next[]数组，避免和头文件next冲突
char s[N], p[M];//s为模式串， p为匹配串

int main()
{
    int n, m;
    cin >> n >> p+1 >> m >> s+1;//s与p的下标从1开始
    //求next数组ne
   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)  //满足匹配条件，打印开头下标, 从0开始
        {
            //匹配完成后的具体操作
            //如：输出以0开始的匹配子串的首字母下标
            printf("%d ", i - n); //(若从1开始，加1)
            j = ne[j];            //再次继续匹配
        }
    }
    return 0;
}