Cod sursa(job #1549232)

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

using namespace std;

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

int ans,v[1010];

void prefix( char N[], int n, int pi[] )
{
    int k = 0,i;
    for( i = 2 ; i <= n ; i++ )
    {
        while( k > 0 && N[ k + 1 ] != N[ i ] )
            k = pi[ k ];

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

        pi[ i ] = k;
    }
}

void KMP( char N[], int n, char M[], int m, int pi[] )
{
    int q = 0,i;

    for( i = 1 ; i <= m ; i++ )
    {
        while( q > 0 && N[ q + 1 ] != M[ i ] )
            q = pi[ q ];

        if( N[ q + 1 ] == M[ i ] )
            q = q + 1;

        if( q == n - 1 && i <= 1000 )
            v[ ++ans ] = i - n + 1;
    }
}

char A[2000010],B[2000010];
int a,b,pi[2000010],i;

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

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

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

    prefix( A , a , pi );
    KMP( A , a , B , b , pi );

    fout<<ans<<'\n';

    for( i = 1 ; i <= ans ; i++ )
        fout<<v[ i ]<< ' ';

return 0;
}