Cod sursa(job #1546687)

Utilizator Vlad.IacobescuIacobescu Vlad Vlad.Iacobescu Data 8 decembrie 2015 17:00:22
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

int z[2000002],n,st,dr,sol[20000],k,m;
char v[2000002],v2[2000002];

ifstream fin ( "strmatch.in" );
ofstream fout ( "strmatch.out" );

int main()
{
    fin.getline( v2 , 20000 );
    fin.getline( v , 200000 );
    //fout << v2;
    //fout << endl;
    //fout << v;
    //fout << endl;
    n = strlen( v2 );
    k = strlen ( v );
    strcat( v2 , "*" );
    strcat( v2 , v );
    //fout << v2 << endl;
    m = strlen( v2 );
    for ( int i=n; i<m; ++i )
    {
        if ( dr >= i )
        {
            z[i] = min( dr - i + 1 , z[i - st] );
        }
        while ( v2[z[i]] == v2[ i + z[i]] )
        {
            ++z[i];
        }
        if ( i + z[i] - 1 > dr )
        {
            dr = i + z[i] - 1;
            st = i;
        }
    }
    k = 0;
    for ( int i = n; i < m; ++i )
    {
        if ( z[i] == n )
        {
            ++k;
            sol[k] = i - n - 1;
        }
    }
    fout << k << endl;
    for ( int i = 1; i <= k; ++i )
        fout << sol[i] << ' ';
    return 0;
}