Cod sursa(job #305972)

Utilizator utcistuBarcau Tomsa utcistu Data 19 aprilie 2009 01:03:21
Problema Potrivirea sirurilor Scor 40
Compilator c Status done
Runda Arhiva educationala Marime 1.02 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXN 200000

char t[MAXN],p[MAXN];
int pref[MAXN];int ok[1000];
int matchNo=0;

int KMP(char *t,char *p,int *pref)
{
    int i,q;
    q=-1;
    for (i=0;i<strlen(t);i++)
    {
        while ((q>=0)&&(p[q+1]!=t[i])) q=pref[q];
        if (p[q+1]==t[i]) q++;
        if (q==strlen(p)-1)
        {
            ok[matchNo++]=i-strlen(p)+1;
            q=pref[q];
        }
    }
    return matchNo;
}

void preCompute(char *p,int *pref)
{
    int i,q;
    q=-1;
    pref[0]=-1;
    for (i=1;i<strlen(p);i++)
    {
        while ((q>=0)&&(p[q+1]!=p[i])) q=pref[q];
        if (p[q+1]==p[i]) q++;
        pref[i]=q;
    }
}

int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    scanf("%s",p);
    scanf("%s",t);
    preCompute(p,pref);
    printf("%d\n",KMP(t,p,pref));
    int i;
    if (matchNo<1000)
    for (i=0;i<matchNo;i++) printf("%d ",ok[i]);
    fclose(stdout);
    return 0;
}