Cod sursa(job #1073414)

Utilizator marta_diannaFII Filimon Marta Diana marta_dianna Data 6 ianuarie 2014 10:29:08
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include<fstream>
#include<cstring>
#define NMAX 2000010
#define MMAX 1010

using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");

char T[NMAX], P[NMAX];
int nT, nP, nr, pi[NMAX], sol[NMAX];

void Citeste()
{
    f.getline(P+1, NMAX); nP=strlen(P+1);
    f.getline(T+1, NMAX); nT=strlen(T+1);
}

void Creaza_pi()
{
    int k=0, i;

    pi[1]=0;

    for (i=2; i<=nP; ++i)
    {
        while (k>0 && P[k+1]!=P[i]) k=pi[k];

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

        pi[i]=k;
    }
}

void KMP()
{
    int k=0, i;

    for (i=1; i<=nT; ++i)
    {
        while (k>0 && P[k+1]!=T[i]) k=pi[k];

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

        if (k==nP)
        {
            sol[++nr]=i-k;

           //if (nr==1000) break;

            k=pi[k];

        }
    }
}

void Scrie()
{
    int i;

    g<<nr<<"\n";

    for (i=1; i<=nr; ++i)
        g<<sol[i]<<" ";
}

int main()
{
    Citeste();

    Creaza_pi();

    KMP();

    Scrie();

    f.close();
    g.close();
    return 0;
}