Pagini recente » Cod sursa (job #2799876) | Cod sursa (job #1598860) | Cod sursa (job #2549928) | Cod sursa (job #1903137) | Cod sursa (job #1160200)
#include <iostream>
#include <cstdio>
#include <cstring>
#define DN 2000005
#define DM 1005
using namespace std;
int pi[DN],n,m,rez[DM],sz;
char x[DN],y[DN];
void make_prefix(){
int k = 0;
pi[1] = 0;
for(int i = 2;i<=n;++i){
while( k && x[k + 1] != x[i])
k = pi[k];
if(x[ k + 1 ] == x[i])
++k;
pi[i] = k;
}
}
void find_ap(){
int k = 0;
for(int i=1;i<=m;++i){
while( k && x[k + 1]!=y[i])
k = pi[k];
if( x[k + 1] == y[i])
++k;
if( k == n ){
++sz;
if(sz<= 1000)
rez[sz] = i - k;
}
}
}
void write(){
cout<<sz<<"\n";
for(int i=1;i<=min(sz,1000);++i)
cout<<rez[i]<<" ";
}
int main()
{
freopen("strmatch.in","r", stdin);
freopen("strmatch.out","w", stdout);
scanf("%s %s",x+1,y+1);
n = strlen(x + 1); m = strlen(y + 1);
make_prefix();
find_ap();
write();
return 0;
}