Cod sursa(job #675506)

Utilizator AplayLazar Laurentiu Aplay Data 7 februarie 2012 17:54:31
Problema Potrivirea sirurilor Scor 18
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include<stdio.h>
#include<string.h>
#define minim(a, b) ((a < b) ? a : b)

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

void citire()
{
    FILE*f=fopen("strmatch.in","r");
    fgets(s,2000005,f);
    fgets(s1,2000005,f);
    for(;(s[n]>='A'&&s[n]<='Z')||(s[n]>='a'&&s[n]<='z')||(s[n]>='0'&&s[n]<='9');++n);
    for(;(s1[m]>='A'&&s1[m]<='Z')||(s1[m]>='a'&&s1[m]<='z')||(s1[m]>='0'&&s1[m]<='9');++m);
    //for (int i = m; i; --i) s1[i] = s1[i-1]; s1[0] = ' ';
    //for (int i = n; i; --i) s[i] = s[i-1]; s[0] = ' ';
    fclose(f);
}

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

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

}

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