Cod sursa(job #1382945)

Utilizator horiainfoTurcuman Horia horiainfo Data 9 martie 2015 19:20:09
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <fstream>
#include <cstring>
#include <cstdio>
#define LGMAX 2000001
using namespace std;
ofstream fout("strmatch.out");
int d,lg,k,L[LGMAX],poz,nr;
char a[LGMAX],b[LGMAX];
void prefix()
{
    d=strlen(a);
    L[0]=-1;
    for(int i=1;i<d;i++)
    {
        k=L[i-1];
        while(k>-1 && a[k+1]!=a[i])
            k=L[k];
        if(a[k+1]==a[i])
            k++;
        L[i]=k;
    }
}
void kmp()
{
    lg=strlen(b);
    poz=0;
    for(int i=0;i<lg;i++)
    {
        if(poz==d)
            nr++,poz=L[poz]+1;
        if(a[poz]==b[i])
            poz++;
        else
            poz=L[poz]+1;
    }
    fout<<nr<<'\n';
}
int main()
{
    freopen("strmatch.in","r",stdin);
    scanf("%s",&a);
    scanf("%s",&b);
    prefix();
    kmp();
    return 0;
}