Cod sursa(job #1389571)

Utilizator bullseYeIacob Sergiu bullseYe Data 16 martie 2015 13:44:34
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <cstdio>
#include <cstring>
#define DMAX 2000010
using namespace std;

char a[DMAX], b[DMAX];
int n, m;
int lg[DMAX];
int lgsol, sol[DMAX];

void citire();
void prefix();
void KMP();
void afisare();

int main()
{
    citire();
    prefix();
    KMP();
    afisare();
    return 0;
}

void citire()
{
    FILE*fin=fopen ("strmatch.in", "r");
    fscanf(fin, "%s", a);
    fscanf(fin, "%s", b);
    n=strlen (a); m=strlen (b);
    fclose(fin);
    return;
}

void prefix()
{
    int i, k;
    lg[1]=0;
    for (i=2; i<=n; ++i)
    {
        k=lg[i-1];
        while (k>0 && a[k+1]!=a[i])
            k=lg[k];
        if (a[k+1]==a[i])
            ++k;
        lg[i]=k;
    }
    return;
}

void KMP()
{
    int i, k=0;
    for (i=1; i<=m; ++i)
    {
        while (k>0 && a[k+1]!=b[i])
            k=lg[k];
        if (a[k+1]==b[i])
            ++k;
        if (k==n)
        {
            sol[++lgsol]=i-n;
            k=lg[k];
        }
    }
    return;
}

void afisare()
{
    int i;
    FILE*fout=fopen ("strmatch.out", "w");
    fprintf(fout, "%d\n", lgsol);
    for (i=1; i<=lgsol; ++i)
        fprintf(fout, "%d ", sol[i]);
    fprintf(fout, "\n");
    fclose(fout);
    return;
}