Pagini recente » Cod sursa (job #2849013) | Cod sursa (job #2614565) | Cod sursa (job #1846429) | Cod sursa (job #1462245) | Cod sursa (job #793915)
Cod sursa(job #793915)
#include<cstdio>
#include<string.h>
#include<cmath>
#define NMAX 2000005
char a[NMAX],b[NMAX];
int n,m;
unsigned int pi[NMAX],ret[1024];
void c_pi()
{
int k=1;
pi[1]=0;
for(int i=2;i<=n;++i)
{
while( k>0 && a[i-1] != a[k+1] )k=pi[k];
if(a[i]==a[k+1])++k;
pi[i]=k;
}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
fgets(a, sizeof(a), stdin);
fgets(b, sizeof(b), stdin);
for (n=0; (a[n] >= 'A' && a[n] <= 'Z') || (a[n] >= 'a' && a[n] <= 'z')|| (a[n] >= '0' && a[n] <= '9'); ++n);
for (m=0; (b[m] >= 'A' && b[m] <= 'Z') || (b[m] >= 'a' && b[m] <= 'z')|| (b[m] >= '0' && b[m] <= '9'); ++m);
for(int i=n;i>0;--i)a[i]=a[i-1];
a[0]=' ';
for (int i=m;i>0;--i)b[i]=b[i-1];
b[0]=' ';
c_pi();
int q=0;
int j=0;
for(int i=1;i<=m;++i)
{
while(q>0 && b[i]!=a[q+1])
q=pi[q];
if(a[q+1]==b[i])++q;
if( q == n)
{
q=pi[n];
++j;
if(j<=1000) ret[j]=i-n;
}
}
printf("%d\n",j);
ret[++j]=-1;
j=1;
while(ret[j]!=-1)
{
printf("%d ",ret[j]);
++j;
}
printf("\n");
return 0;
}