Pagini recente » Cod sursa (job #454934) | Cod sursa (job #3327201) | Cod sursa (job #735871) | Cod sursa (job #735304) | Cod sursa (job #454749)
Cod sursa(job #454749)
#include<stdio.h>
#include<string.h>
#define MAX 2000005
char a[MAX], b[MAX];
long v[MAX],n,m;
void prefix(void)
{
int k,q;
v[0]=0;
k=0;
for(q=2;q<=m;q++)
{
while (k>0 && a[k]!=a[q-1]) k=v[k];
if (a[k]==a[q-1]) k++;
v[q]=k;
}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
gets(a);
gets(b);
m=strlen(a);
n=strlen(b);
prefix();
long q,i;
long ls=0,s[MAX];
q=0;
for (i=1;i<=n;i++)
{
while (q>0 && a[q]!=b[i-1]) q=v[q];
if (a[q]==b[i-1]) q++;
if (q==m)
{
if (ls<1000)
{ls++;
s[ls]=i-m;}
q=v[q];
}
}
printf("%li\n",ls);
for (i=1;i<=ls;i++)
printf("%li ",s[i]);
return 0;
}