Cod sursa(job #344209)

Utilizator marcelcodreaCodrea Marcel marcelcodrea Data 29 august 2009 01:53:53
Problema Potrivirea sirurilor Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include<stdio.h>
#include<string.h>
char A[2000005],B[2000005];
int lA;
int contor;
int sirmatch[1005];
int lB;
int P[2000005];
int now;
int min(int r1, int r2)
{
    if (r1 < r2) return r1;
    return r2;
}
void Prefix()
{
    int now = 0;

    for(int i = 1; i < lA; i++)
     {
         //now = P[i-1];
         while (A[now] != A[i] && now > 0)
           {
               now = P[now];
           }
         if (A[now] == A[i]) now++;
         P[i] = now;
     }

}

int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);

    scanf("%s %s",&A,&B);
    lA = strlen(A);
    lB = strlen(B);
    Prefix();
    now = 0;
    for(int i = 0; i < lB; i++)
     {
         while (A[now] != B[i] && now > 0)
           {
               now = P[now];
           }
         if (A[now] == B[i])
          now++;
         if (now == lA)
          {

              contor++;
              if (contor <= 1000)
              {
              sirmatch[contor] = i - lA + 1;
              }
              now = P[lA-1];
          }

     }
     printf("%d\n",contor);
     for(int i = 1; i <= min(contor,1000);i++)
      printf("%d ",sirmatch[i]);



    return 0;
}