Pagini recente » Cod sursa (job #3171397) | Cod sursa (job #2359835) | Cod sursa (job #1204677) | Cod sursa (job #2686723) | Cod sursa (job #2417389)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#define N 2000005
using namespace std;
char a[N], txt[N];
int lp[N];
int lena, lenb;
vector <int> sol;
inline void prefix(){
int j = 0;
for(int i = 1; i < lena; ++i){
if(a[i] == a[j])
lp[i] = ++j;
else{
--j;
while(j>=0){
j=lp[j];
if(a[i] == a[j]){
lp[i] = ++j;
break;
}else
--j;
}
if(j<0)
lp[i] = j = 0;
}
}
}
inline void kmp(){
int i, j;
while(i<lenb){
if(a[j] == txt[i])
++i, ++j;
if(j==lena){
sol.push_back(i-lena);
j=lp[j-1];
}
else if(i<lenb && a[j]!=txt[i]){
if(j!=0)
j = lp[j-1];
else
++i;
}
}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
fgets(a,N,stdin);
fgets(txt,N,stdin);
lena = strlen(a) - 1;
lenb = strlen(txt) - 1;
prefix();
kmp();
cout<<sol.size()<<"\n";
int len = sol.size();
len = min(len, 1000);
for(int i = 0; i < len; ++i)
cout<<sol[i]<<" ";
return 0;
}