Cod sursa(job #218546)

Utilizator RobybrasovRobert Hangu Robybrasov Data 2 noiembrie 2008 14:26:49
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 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)
        {
            rez[++kont]=i-m;
            if (kont>=1000) return;
            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<=kont; i++) printf("%d ",rez[i]);
    //for (i=1; i<=m; i++) printf("%d ",poz[i]);

    return 0;
}