Cod sursa(job #1083569)

Utilizator httpsLup Vasile https Data 16 ianuarie 2014 06:47:00
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <iostream>
#include <fstream>
#include <string>

using namespace std;

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

#define cout g
string sablon,text;
int l[2000002],v[1001],n,m;

void calculeaza_l()
{
    int i,k;
    for(i=2; i<=m; ++i)
    {
        k=l[i-1];
        while (k && sablon[k+1]!=sablon[i]) k=l[k];
        if(sablon[k+1]==sablon[i]) k++;
        l[i]=k;
    }
}
int main()
{
    f>>sablon>>text;
    sablon=' '+sablon;
    text=' '+text;
    m=sablon.length()-1;
    n=text.length()-1;
    //cout<<sablon[3];
    calculeaza_l();
    int k=0,i,nr(0);
    //cout<<text.length();
    for(i=1; i<=n; i++)
    {
        while(k && sablon[k+1]!=text[i]) k=l[k];
        if(sablon[k+1]==text[i])++k;
        if(k==m)
        {
            ++nr;
            if(nr<=1000)v[nr]=i-m;
            k=l[k];
        }
    }
    cout<<nr<<'\n';
    for(i=1; i<=min(1000,nr); ++i)cout<<v[i]<<' ';

    return 0;
}