Cod sursa(job #228784)

Utilizator marcelcodreaCodrea Marcel marcelcodrea Data 7 decembrie 2008 23:37:07
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include<stdio.h>
#include<string.h>


char a[2000001],b[2000001];
int P[2000001];
int l;
int nr;
int k;
int poz[1005];

void Prefix_Kmp()
{
    P[1] = 0;
    int k = 0;
    l = strlen(a);
    for(int i = 2; i <= l; 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);
    Prefix_Kmp();
    k = 0;
    int lb = strlen(b);
    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 == l)
        {
            nr++;
            if (nr<1000)
            poz[++poz[0]] = i-l;
        }
     }
     printf("%d \n", nr);
     for(int i = 1; i <= poz[0]; i++)
      printf("%d ",poz[i]);
     return 0;
}