Cod sursa(job #238599)

Utilizator free2infiltrateNezbeda Harald free2infiltrate Data 2 ianuarie 2009 18:05:36
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#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]);

}