Cod sursa(job #2366524)

Utilizator DysKodeTurturica Razvan DysKode Data 4 martie 2019 20:39:35
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#include <bits/stdc++.h>

using namespace std;

#define x first
#define y second

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

char a[2000010],b[2000010];
int pi[2000010],i,j,n,m,k,v[1010],ans;

int main()
{
    fin.get( a + 1 , 2000010 );
    fin.get();
    fin.get( b + 1 , 2000010 );

    n = strlen( a + 1 );
    m = strlen( b + 1 );

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

    k = 0;
    for( i = 1 ; i <= m ; i++ )
    {
        while( k > 0 && a[ k + 1 ] != b[ i ] )
            k = pi[ k ];
        if( a[ k + 1 ] == b[ i ] )
            k = k + 1;
        if( k == n )
        {
            ++ans;
            if( ans <= 1000 )
                v[ ans ] = i - n;
            k = pi[ k ];
        }
    }

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

return 0;
}