Cod sursa(job #675457)

Utilizator AplayLazar Laurentiu Aplay Data 7 februarie 2012 17:11:53
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include<stdio.h>
#include<string.h>

char s[2000010],s1[2000010];
int pi[2000010],n,m,nr,poz[2000010],p;

void citire()
{
    FILE*f=fopen("strmatch.in","r");
    n=m=1;
    while(fscanf(f,"%c",&s[n])&&s[n]!='\n')
        ++n;
    s[n--]=NULL;
    while(fscanf(f,"%c",&s1[m])&&s1[m]!='\n')
        ++m;
    s1[m--]=NULL;
    fclose(f);
}

void kmp_prefix()
{
    pi[1]=0;
    int k=0;
    for(int i=2;i<=n&&s[i];++i)
    {
        while(k>0 && s[k+1]!=s[i])
             k=pi[k];
        if(s[k+1] == s[i] )
           {  ++k;  }
        pi[i]=k;
    }
}

void kmp()
{
    int k=0;
    for(int i=1;i<=m;++i)
    {
        while(k>0 && s[k+1]!=s1[i])
            { k=pi[k]; p=i-k; }
        if(s[k+1]==s1[i])
            { ++k; if(k==1) p=i; }
        if(k == n)
            poz[++nr]=p;
    }
}

int main()
{
    citire();
    kmp_prefix();
    kmp();
    FILE*f=fopen("strmatch.out","w");
    fprintf(f,"%d\n",nr);
    for(int i=1;i<=nr;++i) fprintf(f,"%d ",poz[i]-1);
    fclose(f);
    return 0;
}