Cod sursa(job #895499)

Utilizator Eugen01Vasilescu Eugen Eugen01 Data 27 februarie 2013 11:37:00
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include<fstream>
#include<cstring>
#include<vector>
#define Nmax 2000009
#define pb push_back

using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");

int nr,phi[Nmax],i,q,N,M;
char s1[Nmax],s2[Nmax];
vector<int> Q;

void prefix()
{
    phi[0]=0;
    i=1;
    q=0;
    while (i<N)
    {
        while (s1[q]!=s1[i] && q)
            q=phi[q-1];
        if (s1[q]==s1[i]) q++;

        phi[i]=q;
        i++;
    }
}

void KMP()
{
    i=0;
    q=0;
    while (i<M)
    {
        while (s1[q]!=s2[i] && q)
            q=phi[q-1];

        if (s1[q]==s2[i]) q++;

        if (q==N)
        {
            nr++;
            if (nr<=1000) Q.pb(i-N+1);
        }
        i++;
    }
}



int main()
{
    in.getline(s1,Nmax);
    in.getline(s2,Nmax);
    N=strlen(s1);
    M=strlen(s2);

    prefix();
    KMP();
    out<<nr<<'\n';
    for (i=0;i<Q.size();i++)
        out<<Q[i]<<' ';
}