Cod sursa(job #1801413)

Utilizator mihnea00Duican Mihnea mihnea00 Data 8 noiembrie 2016 23:06:43
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
//Potrivire-KMP
#include <fstream>
#include <cstring>

using namespace std;

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

int n1,n2,i,k,q,nr,p[20000010],v[20000010],Max;
char sir1[20000010],sir2[20000010];

int main()
{
    fin>>sir1;
    fin>>sir2;
    //fout<<sir1<<"\n"<<sir2;
    n1=strlen(sir1);
    n2=strlen(sir2);
    p[1]=0;
    for(i=2;i<=n1;++i)
    {
        while(k>0 && sir1[k]!=sir1[i-1])
            k=p[k];
        if(sir1[k]==sir1[i-1])
            k++;
        p[i]=k;
    }
    for(i=0;i<n2;++i)
    {
        while(q>0 && sir1[q]!=sir2[i])
            q=p[q];
        if(sir1[q]==sir2[i])
            q++;
        if(q==n1)
        {
            ++nr;
            v[nr]=i-n1+1;
        }
    }
    Max=min(nr,1000);
    fout<<nr<<"\n";
    for(i=1;i<=Max;++i)
    {
        fout<<v[i]<<" ";
    }
    return 0;
}