Cod sursa(job #305980)

Utilizator utcistuBarcau Tomsa utcistu Data 19 aprilie 2009 01:37:25
Problema Potrivirea sirurilor Scor 14
Compilator c Status done
Runda Arhiva educationala Marime 1.35 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define MAXN 300000

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

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

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

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