#include <bits/stdc++.h>

using namespace std;

//kmp算法

//构建next数组

vector<int> getNext(string s){

   vector<int> nt(s.size()+1,0);

   int i=0,j=-1;

   nt[i]=j;

   while(i<=s.size()){

       if(j==-1||s[i]==s[j]) nt[++i]=++j;

       else j=nt[j];

   }

   return nt;

}

//KMP搜索

vector<int> KMPSearch(string s,string t){

   vector<int> ans,nt=getNext(t);

   int i=0,j=0;

   while(i<s.size()){

       while(j!=0&&s[i]!=t[j]) j=nt[j];

       if(s[i]==t[j]) j++;

       if(j==t.size()) ans.push_back(i-j+1);

       i++;

   }

   return ans;

}

//1467 通过前后缀相同，将前缀+中间位置的内容复制一份，则前后缀重合，因此长度为总长-前后缀长

//1468 找最短相同前后缀

int main(){

   vector<int> k=KMPSearch("abcdabcd","abc");

   for(int i=0;i<k.size();i++) cout<<k[i]<<" ";

   return 0;

}