Cod sursa(job #1135222)

Utilizator lupvasileLup Vasile lupvasile Data 7 martie 2014 15:12:10
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>

using namespace std;

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

#define lmax 2000002
#define cout g

char p[lmax],text[lmax];
int ff[lmax];
int n,m,nr;

void make_prefix()
{
    int i,v;
for(i=2;i<=n;++i)
{
        v=i-1;
        while (p[i]!=p[ff[v]+1] && v) v=ff[v];
        if(p[i]==p[ff[v]+1]) ff[i]=ff[v]+1;
}
}
vector <int> sol;
void kmp()
{
    int i,j(0);
    for(i=1;i<=m;++i)
    {
        while (text[i]!=p[j+1] && j) j=ff[j];
        if(text[i]==p[j+1])++j;
        if(j==n)
        {
            if(sol.size()<=1000) sol.push_back(i-n);
            j=ff[j];
            ++nr;
        }

    }
}
int main()
{
    f>>p+1;
    f>>text+1;
    n=strlen(p+1);m=strlen(text+1);
    make_prefix();
//for(int i=1;i<=n;++i)cout<<ff[i]<<' ';
    kmp();
    cout<<nr<<'\n';
    for(int i=0;i<min((int)sol.size(),1001);++i)cout<<sol[i]<<' ';
    return 0;
}