Pagini recente » Cod sursa (job #2770953) | Cod sursa (job #230665) | Cod sursa (job #354062) | Cod sursa (job #2771610) | Cod sursa (job #238599)
Cod sursa(job #238599)
#include <stdio.h>
#include <string.h>
char A[2000001],B[2000001];
int p[2000001],sol[1001],nr,m,n;
int min(int x,int y)
{
if (x>y) return y;
return x;
}
void prefix()
{
int k = 0,i;
for (i=2;i<=m;i++)
{
while (k>0 && A[k+1]!=A[i]) k = p[k];
if (A[k+1]==A[i]) k++;
p[i] = k;
}
}
void kmp()
{
int q=0,i;
for (i=1;i<=n;i++)
{
while (q>0 && A[q+1]!=B[i]) q = p[q];
if (A[q+1]==B[i]) q++;
if (q==m) {
if (nr<1000) sol[nr++] = i-m;
else nr++;
q=p[q];
}
}
}
int main()
{
FILE *in = fopen("strmatch.in","r");
FILE *out = fopen("strmatch.out","w");
fscanf(in,"%s\n",A);
fscanf(in,"%s",B);
m = strlen(A);
n = strlen(B);
int i;
for (i=m;i;i--) A[i] = A[i-1];
for (i=n;i;i--) B[i] = B[i-1];
prefix();
kmp();
fprintf(out,"%d\n",nr);
for (i=0;i<min(1000,nr);i++) fprintf(out,"%d ",sol[i]);
}