Cod sursa(job #1389908)

Utilizator raztaapDumitru raztaap Data 16 martie 2015 18:47:39
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 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,v[1001];
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=-1;
    for(int i=0;i<lg;i++)
    {
        while(poz>=0 && a[poz+1]!=b[i])
            poz=L[poz];
        if(a[poz+1]==b[i])
            poz++;
        if(poz==d-1)
        {
            nr++;
            poz=L[poz];
            if(nr<=1000)
                v[nr]=i-d+1;
        }
    }
    fout<<nr<<'\n';
    for(int i=1;i<=nr && i<=1000;i++)
        fout<<v[i]<<' ';
}
int main()
{
    freopen("strmatch.in","r",stdin);
    scanf("%s",&a);
    scanf("%s",&b);
    prefix();
    kmp();
    return 0;
}