Cod sursa(job #344244)

Utilizator marcelcodreaCodrea Marcel marcelcodrea Data 29 august 2009 13:39:12
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 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 = 2; i < lA; i++)
     {
         //now = P[i-1];
         while (A[now] != A[i-1] && now > 0)
           {
               now = P[now];
           }
         if (A[now] == A[i-1]) now++;
         P[i] = now;
     }

}

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

    scanf("%s %s",&A,&B);
    lA = strlen(A);
    lB = strlen(B);
    Prefix();
    now = 1;
    for(int i = 1; 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] + 1;
          }

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



    return 0;
}