Pagini recente » Cod sursa (job #818606) | Cod sursa (job #888130) | Cod sursa (job #62160) | Cod sursa (job #882474) | Cod sursa (job #238597)
Cod sursa(job #238597)
#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 = -1,i;
for (i=1;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=-1,i;
for (i=0;i<n;i++)
{
while (q>0 && A[q+1]!=B[i]) q = p[q];
if (A[q+1]==B[i]) q++;
if (q==m-1) {
if (nr<1000) sol[nr++] = i-m+1;
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);
prefix();
kmp();
fprintf(out,"%d\n",nr);
for (int i=0;i<min(1000,nr);i++) fprintf(out,"%d ",sol[i]);
}