Cod sursa(job #1923375)

Utilizator DysKodeTurturica Razvan DysKode Data 10 martie 2017 23:11:15
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <bits/stdc++.h>

using namespace std;

#define f first
#define s second

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

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

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;
        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;
        if( k == n )
        {
            ++ans;
            if( ans <= 1000 )
                sol[ ans ] = i - n;
            k = pi[ k ];
        }
    }

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

return 0;
}