Cod sursa(job #229630)

Utilizator marcelcodreaCodrea Marcel marcelcodrea Data 10 decembrie 2008 21:33:03
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include<stdio.h>
#include<string.h>
char a[2000005];
char b[2000005];
int P[2000005];
int sir[1002];
int nr;
int la;
int k;
int lb;
void Kmprefix()
{
    int k = 0;
    for(int i = 2; i <= la; i++)
     {
         while (k > 0 && a[k] != a[i-1])
          k = P[k];
         if (a[k] == a[i-1]) k++;
         P[i] = k;
     }
}
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    scanf("%s %s",&a,&b);
    la = strlen(a);
    lb = strlen(b);
    Kmprefix();
    k = 0;
    for(int i = 1; i <= lb; i++)
     {
         while (k > 0 && a[k] != b[i-1])
          k = P[k];
         if (a[k] == b[i-1]) k++;
         if (k == la)
          {
              nr++;
              if (nr <= 1000)
               sir[++sir[0]] = i - la;
          }
     }
    printf("%d \n",nr);
    for(int i = 1;i <= sir[0]; i++)
     printf("%d ",sir[i]);
    return 0;
}