Cod sursa(job #1707064)

Utilizator SirStevensIonut Morosan SirStevens Data 24 mai 2016 08:47:59
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <bits/stdc++.h>

using namespace std;

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

#define Nmax 2000005
string N,M;
int k,pi[Nmax],q,m,n,nr,pos[Nmax];

void make_prefix(){

    pi[1]=0;
    for(int i=2;i<=n;i++){

        while(k && N[i+1]!=N[i]){
            k=pi[k];

        }
        if(N[k+1]==N[i])
            k++;
        pi[i]=k;
    }

}

void alg_KMP(){

    for(int i=1;i<=m;i++){

        while(q && N[q+1]!=M[i])
            q=pi[q];
        if(N[q+1] == M[i])
            q++;
        if(q == n){
            q=pi[n];
            nr++;
            if(nr <= 1000)
                pos[nr]=i-n;
        }
    }


}

int main()
{
    getline(in,N);
    getline(in,M);
    n=N.size();
    m=M.size();
    make_prefix();
    alg_KMP();
    out<<nr<<'\n';
    for(int i=1;i<=min(nr,1000);i++)
        out<<pos[i]<<" ";
    return 0;
}