Pagini recente » Cod sursa (job #2172528) | Cod sursa (job #96956) | Cod sursa (job #2145255) | Cod sursa (job #189330) | Cod sursa (job #192899)
Cod sursa(job #192899)
#include <stdio.h>
#include <string.h>
#define ui unsigned long int
#define maxl 200010
#define baz 65
ui i,j,k,n,m,val,put,nr;
char A[maxl],B[maxl],trans[maxl];
int poz[maxl],abc[256];
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s",A+1);A[0]=' ';
n=strlen(A)-1;
scanf("%s",B+1);B[0]=' ';
m=strlen(B)-1;
k=0;
for (i=48; i<=57; i++) abc[i]=++k;
for (i=65; i<=90; i++) abc[i]=++k;
for (i=97; i<=122; i++) abc[i]=++k;
k=0;
for (i=1; i<=n-1; i++)
{
val=val*baz+abc[A[i]];
k=k*baz+abc[B[i]];
}
val=val*baz+abc[A[n]];
put=1;
for (i=1; i<=n; i++) put*=baz;
B[0]='*';abc[42]=0;
for (i=n; i<=m; i++)
{
k=k*baz+abc[B[i]];
k-=put*(abc[B[i-n]]);
if (k==val)
poz[++nr]=i-n;
}
printf("%d\n",nr);
if (nr>1000) nr=1000;
for (i=1; i<=nr; i++)
printf("%d ",poz[i]);
return 0;
}