Cod sursa(job #1647657)

Utilizator DysKodeTurturica Razvan DysKode Data 10 martie 2016 21:31:25
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <fstream>
#include <cstring>

using namespace std;

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

int Z[4000010],i,j,n,m,k,l,r,ans[1010];
char S[4000010];

void expand()
{
    while( S[ r + 1 ] == S[ r - l + 1 ] && r + 1 < n ) r++;
}

int main()
{
    fin.get( S , 2000010 );
    fin.get();
    n = strlen( S );
    k = n;
    Z[ 0 ] = k;
    S[ n ] = '$';
    fin.get( S + n + 1 , 2000010 );
    n = strlen( S );

    r = l = 0;
    for( i = 1 ; i < n ; i++ )
    {
        Z[ i ] = 0;
        if( l <= i && i <= r )
        {
            if( i + Z[ i - l ] <= r )
                Z[ i ] = Z[ i - l ];
            else
            {
                l = i;
                expand();
                Z[ i ] = r - l + 1;
            }
        }
        else if( S[ i ] == S[ 0 ] )
        {
            l = r = i;
            expand();
            Z[ i ] = r - l + 1;
        }
        if( Z[ i ] == k )
        {
            ++ans[ 0 ];
            if( ans[ 0 ] <= 1000 )
                ans[ ans[ 0 ] ] = i - k - 1;
        }
    }

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


return 0;
}