Pagini recente » Cod sursa (job #646669) | Cod sursa (job #464656) | Cod sursa (job #213212) | Cod sursa (job #1147657) | Cod sursa (job #759119)
Cod sursa(job #759119)
#include <cstdio>
#include <algorithm>
using namespace std;
#define MAX 1<<21
int n,nr,pos[1001],u[MAX];
char a[MAX],b[MAX];
void prefix(){
int k=-1;
u[0]=k;
for(int i=1;a[i]!='\n' && a[i]!='\0';n=i++)
{
while(k>-1 && a[k+1]!=a[i])k=u[k];
if(a[k+1]==a[i])k++;
u[i]=k;
}
}
void kmp(){
int k=-1;
for(int i=0;b[i]!='\n' && b[i]!='\0';i++)
{
while(k>-1 && a[k+1]!=b[i])k=u[k];
if(a[k+1]==b[i])k++;
if(k==n)
{
nr++;
if(nr<=1000)pos[nr]=i-k;
k=u[k];
}
}
}
int main(){
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s ",a);
scanf("%s ",b);
prefix();
kmp();
printf("%d\n",nr);
for(int i=1;i<=min(1000,nr);i++)printf("%d ",pos[i]);
return 0;
}