Cod sursa(job #919351)

Utilizator VisuianMihaiMihai Visuian VisuianMihai Data 19 martie 2013 16:51:22
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <fstream>
#include <string>

using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string p, t;
int urm[2000001], sol[2000001], n, m, nr;
void ComputePrefix(string p)
{
    int k=-1;
    urm[0]=0;
    for ( int x = 1; x < m; x++ )
    {
        while(k > 0 && p[k+1] != p[x] )
            k = urm[k];
        if ( p[k+1] == p[x] ) k++;
        urm[x] = k;
    }
}
int main()
{
    int x = -1;
    fin >> p >> t;
    m = p.size(),n = t.size();
    ComputePrefix(p);
    for ( int i = 0; i < n; i++ )
    {
        while (x > 0 && p[x+1] != t[i] )
            x = urm[x];
        if (p[x+1] == t[i]) x++;
        if ( x == m-1)
            sol[++nr] = i-m+1;
    }
    fout << nr << '\n';
    for ( int i = 1; i<= min(nr,1000); i++ )
        fout << sol[i] << ' ';
    fin.close();
    fout.close();
    return 0;
}