题目描述

C++代码

样例

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;
const int N=1e6+10;
int n,m;
string p;
string s;
void strStr(const string& haystack, const string& needle) {
        string str=needle+'#'+haystack;
        vector<int> pi(str.size());
        for(int i=1;i<str.size();i++)
        {
            int len=pi[i-1];
            while(len && str[i]!=str[len])
            {
                len=pi[len-1];
            }
            if(str[len]==str[i])
            {
                pi[i]=len+1;
                if(pi[i]==needle.size())
                {
                    cout << i-2*needle.size() << " ";
                }
            }
        }
    }
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> p >> m >> s;

    strStr(s,p);
    return 0;
}