Cod sursa(job #218547)

Utilizator RobybrasovRobert Hangu Robybrasov Data 2 noiembrie 2008 14:31:28
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <stdio.h>
#include <string.h>
#define N 2000100

char t[N],p[N];
int poz[N],m,i,n,rez[1010],kont;

void prefix()
{
    int i,k=0;
    for (i=2; i<=m; i++)
    {
        while (k && p[k+1]!=p[i]) k=poz[k];
        if (p[k+1]==p[i]) k++;
        poz[i]=k;
    }
}

void kmp()
{
    int i,k=0;
    for (i=1; i<=n; i++)
    {
        while (k && p[k+1]!=t[i]) k=poz[k];
        if (p[k+1]==t[i]) k++;
        if (k==m)
        {
            if (kont<1000) rez[++kont]=i-m;
            else kont++;
            k=poz[k];
        }
    }
}

int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    fgets(p+1,N,stdin);
    fgets(t+1,N,stdin);
    m=strlen(p+1)-1;
    n=strlen(t+1)-1;
    kont=0;
    prefix();
    kmp();
    printf("%d\n",kont);
    for (i=1; i<=1000; i++) printf("%d ",rez[i]);

    return 0;
}