Cod sursa(job #186558)

Utilizator VmanDuta Vlad Vman Data 28 aprilie 2008 12:27:06
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
using namespace std;
#include <cstdio>
#include <cstring>

#define Lmax 2000001

int nr,L1,L2;
char A[Lmax],B[Lmax];
int T[Lmax];
int P[1001];

void buildT()
{
 int i,k;
 T[0]=-1;
 k=-1;
 for (i=1; i<L1; ++i)
     {
      while (A[k+1] != A[i] && k>=0)
            k=T[k];
      if (A[k+1] == A[i]) ++k;
      T[i]=k;
     }
}

void kmp()
{
 int i,k;
 k=-1;
 for (i=0; i<L2; ++i)
     {
      while (A[k+1] != B[i] && k>=0)
            k=T[k];
      if (A[k+1] == B[i]) ++k;
      if (k==L1-1)
        if (nr<1000)
          P[nr++]=i-L1+1;
          else ++nr;
     }
}

int main()
{
 int i;
 freopen("strmatch.in","r",stdin);
 freopen("strmatch.out","w",stdout);
 scanf("%s\n",&A);
 scanf("%s\n",&B);
 L1=strlen(A);
 L2=strlen(B);
 buildT();
 kmp();
 printf("%d\n",nr);
 for (i=0; i<nr && i<1000; ++i)
     printf("%d ",P[i]);
 fclose(stdout);    
 return 0;
}