Pagini recente » Cod sursa (job #2945514) | Cod sursa (job #1832391)
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
char s[200001], a[200001];
int n, m;
int fix(int k){
int aux[200001]={0};
int j=0, i=1;
while(i<=k){
if(a[i]==a[j]){
aux[i]=j+1;
j++;
}
else{
while(j>0){
j=aux[j-1];
if(a[i]==a[j]){
aux[i]=j+1;
j++;
break;
}
}
}
i++;
}
return aux[n-1];
}
int kjh[1000];
int k=0;
int kmp(){
int nr=0;
int i=0, j=0, ok=0;
while(i<m)
{
if(a[j]==s[i])
{
j++;
ok=1;
}
else if(ok==1){
j=fix(j-1);
ok=0;
}
if(j==n && ok==1 && nr<=1000)
{nr++;
kjh[k++]=i-n+1;
j=fix(j-1);
ok=0;}
i++;
}
return nr;
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
cin.getline(a, 200001);
cin.getline(s, 200001);
n=strlen(a);
m=strlen(s);
cout<<kmp()<<endl;
for(int i=0; i<k; i++)
cout<<kjh[i]<<" ";
return 0;
}