Cod sursa(job #919563)

Utilizator VisuianMihaiMihai Visuian VisuianMihai Data 19 martie 2013 18:51:52
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include<fstream>
#include<string>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string p,t;
int m,n,nr,urm[2000001], sol[2000001];

void ComputePrefix(string p)
{
    int k = -1;
    urm[0] = -1;
    for ( int x = 1; x < m; x++ )
    {
        while ( k>-1 && 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>-1 && p[x+1] != t[i] )
            x = urm[x];
        if ( p[x+1] == t[i] )
            x++;
        if(x==m-1)
        {
            nr++;
            if ( nr <= 1000 )
                sol[nr] = i-m+1;
            x = urm[m-1];
        }
    }
    fout << nr << '\n';
    for ( int i = 1; i <= min(1000,nr); i++ )
        fout << sol[i] << ' ';
    fin.close();
    fout.close();
}