KMP模板，注释

#include<bits/stdc++.h>
using namespace std;
queue<int> KMP(string a,string b){//a是主串，b是模式串，返回出现位置的下标，如果没有则返回的队列empty()
    queue<int> ans;
    int i=0,j=0;//用于比对两个串的下标
    int next[b.length()+1];//在下标i之前的字符串前后缀相同的最长长度。
    next[0]=0;next[1]=0;
    for(int f=2;f<=b.length();f++){//计算next，注意初始化[0]和[1]
        while(j>0&&b[j]!=b[f-1])
            j=next[j];
        if(b[f-1]==b[j])j++;
        next[f]=j;
    } j=0;
    int box=0;
    for(;i<a.length()&&a.length()-i>=b.length()-1;i++){//匹配过程
         int pointer =i;
         for(;;j++){
             if(a[pointer]!=b[j]&&j==0){//如果通过next回到串头，且串头字符仍然匹配失败，则break使i++
                 j=0;
                 break;
             }else if(a[pointer]!=b[j]){//如果当前字符匹配失败，则通过next到达下一个位置
                 j=next[j];
                 i = pointer-1;
                 break;
             }else if(b.length()==1){//排除特殊情况：字符串长度为1时，匹配成功依然要挪动指针 i
                 j=0;
                 ans.push(i);
                 break;
             }else if(j==b.length()-1){//字符串匹配完成，添加答案到队列，并通过next到达下一个位置
                 j=next[j];
                 ans.push(i-box);
                 box = j;
                 i=pointer-1;
                 break;
             }
             pointer++;
         }
    }
    return ans;
}

int main(){
    string s1,s2;cin>>s1>>s2;
    queue<int> que = KMP(s1,s2);
    while(!que.empty()){
        cout<<que.front()<<" ";
        que.pop();
    }
}