Cod sursa(job #552366)

Utilizator bogfodorBogdan Fodor bogfodor Data 12 martie 2011 10:15:59
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <cstdio>
#include <cstring>
#define lmax 2000005

using namespace std;

FILE *fin=freopen("strmatch.in","r",stdin);
FILE *fout=freopen("strmatch.out","w",stdout);

char a[lmax],b[lmax];
int m,n,p[lmax],ap[1001],k=0;

void citire()
{
    scanf("%s\n%s",a,b);
    m=strlen(a);
    n=strlen(b);
}

void prefix()
{
    int i=0,j=-1;
    p[i]=j;
    while(i<m)
    {
        while(j>=0 && a[i]!=a[j])
            j=p[j];
        i++; j++;
        p[i]=j;
    }
}

void cauta()
{
   int i=0,j=0;
   while(i<n)
   {
        while(j>=0 && b[i]!=a[j])
            j=p[j];
        i++;
        j++;
       if(j==m)
       {
        if(k<1000)
            ap[k++]=i-j;
        else
            k++;
        j=p[j];
        }

}
}

void afisare()
{
  printf("%d\n",k);
  for(int i=0; i<k && i<1000;i++)
        printf("%d ", ap[i]);
}

int main()
{
    citire();
    prefix();
    cauta();
    afisare();
    return 0;
}