Cod sursa(job #1804895)

Utilizator AlexandraIrimiaAlexandra Irimia AlexandraIrimia Data 13 noiembrie 2016 10:58:50
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int urm[2000001],m,n,v[2000001],l;
char t[2000001],p[2000001];
void prefix()
{
    int q,k;
    k=0;
    urm[1]=0;
    for(q=2; q<=m; q++)
    {
        while(k>0 && p[k]!=p[q-1])k=urm[k];
        if(p[k]==p[q-1])k++;
        urm[q]=k;
    }
    /* for(q=1;q<=m;q++)
         cout<<urm[q]<<" ";cout<<endl;*/
}
void kmp()
{
    int q,nr=0,k=0;
    for(q=0; q<n; q++)
    {
        while(k>0 && p[k]!=t[q])
            k=urm[k];
        if(p[k]==t[q])k++;
        if(k==m)
        {
            v[++nr]=q-m+1;
        }
    }
    g<<nr<<'\n';
    for(int i=1;i<=nr && i<=1000;i++)
        g<<v[i]<<" ";
}
int main()
{
    f.getline(p,2000001);
    f.getline(t,2000001);
    n=strlen(t);
    m=strlen(p);
    prefix();
    kmp();
    return 0;
}