Cod sursa(job #1389918)

Utilizator Arodoet96Teodora Stoleru Arodoet96 Data 16 martie 2015 18:53:33
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include <fstream>
#include <cstring>
#define TMAX 2000004//100000
#define PMAX 2000004//1000

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

int n, m;
char T[TMAX], P[PMAX];
int prefix[PMAX];
int match[PMAX], nrmatch;

void citire();
void calcul_prefix();
void KMP();
void afisare();

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

void citire()
{
    //fin>>n>>m;
    fin>>P+1>>T+1;
    n=strlen(T+1);
    m=strlen(P+1);
}

void calcul_prefix()
{
    int p, k;
    prefix[1]=0;
    for(p=2;p<=m;++p)
    {
        k=prefix[p-1];

        while(k>0 && P[k+1]!=P[p])
            k=prefix[k];

        if(P[k+1]==P[p])
            ++k;

        prefix[p]=k;
    }
}

void KMP()
{
    int t, k=0;
    for(t=1;t<=n;++t)
    {
        while(k>0 && P[k+1]!=T[t])
            k=prefix[k];

        if(P[k+1]==T[t])
            ++k;

        if(k==m)
        {
            match[++nrmatch]=t-m;
            k=prefix[k];
        }
    }
}

void afisare()
{
    int i;
    fout<<nrmatch<<'\n';
    for(i=1;i<=nrmatch;++i)
        fout<<match[i]<<' ';
}