Cod sursa(job #1549236)

Utilizator DysKodeTurturica Razvan DysKode Data 12 decembrie 2015 03:18:51
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <fstream>
#include <cstring>

using namespace std;

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

char A[2000010],B[2000010];
int pi[2000010],ans[1010],i,j,a,b,sol,k;

int main()
{
    fin.get( A + 1 , 2000010 ); fin.get();
    fin.get( B + 1 , 2000010 );
    A[ 0 ] = ' ';
    B[ 0 ] = ' ';

    a = strlen( A );
    b = strlen( B );

    for( i = 2 ; i <= a ; i++ )
    {
        while( k > 0 && A[ k + 1 ] != A[ i ] )
            k = pi[ k ];

        if( A[ k + 1 ] == A[ i ] )
            k++;

        pi[ i ] = k;
    }

    for( i = 1 ; i <= b ; i++ )
    {
        while( k > 0 && A[ k + 1 ] != B[ i ] )
            k = pi[ k ];

        if( A[ k + 1 ] == B[ i ] )
            k++;

        if( k == a - 1 )
        {
            ++sol;
            if( sol <= 1000 )
                ans[ sol ] = i - a + 1;
        }
    }

    fout<<sol<<'\n';
    for( i = 1 ; i <= min( sol , 1000 ) ; i++ )
        fout<<ans[ i ]<<' ';

return 0;
}