Cod sursa(job #1549646)

Utilizator DysKodeTurturica Razvan DysKode Data 12 decembrie 2015 16:17:59
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <fstream>
#include <cstring>

using namespace std;

#define NMAX 2000010

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

char N[ NMAX ], M[ NMAX ];
int n,m,k,q,pi[ NMAX ],ans,v[1010],i;

int main()
{
    fin.get( N + 1 , NMAX ); fin.get();
    fin.get( M + 1 , NMAX );
    N[ 0 ] = ' ';
    M[ 0 ] = ' ';

    n = strlen( N );
    m = strlen( M );

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

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

        pi[ i ] = k;
    }

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

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

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

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

return 0;
}