Cod sursa(job #1630890)

Utilizator DysKodeTurturica Razvan DysKode Data 5 martie 2016 11:53:23
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <fstream>
#include <string>

using namespace std;

int Z[4000010],i,j,n,m,l,r,k,ans[1010];
string a,b;

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

void expand()
{
    while( a[ r + 1 ] == a[ r - l + 1 ] && r <= a.size() )
        r++;
}

int main()
{
    fin>>a;
    k = a.size();
    Z[ 0 ] = k;
    a += "$";
    fin>>b;
    a += b;
    for( i = 1 ; i < a.size() ; i++ )
    {
        Z[ i ] = 0;
        if( l <= i && i <= r )
        {
            if( Z[ i - l ] >= r - i + 1 )
            {
                l = i;
                expand();
                Z[ i ] = r - l + 1;
            }
            else
                Z[ i ] = Z[ i - l ];
        }
        else if( a[ i ] == a[ 0 ] )
        {
            l = r = i;
            expand();
            Z[ i ] = r - l + 1;
        }
        if( Z[ i ] == k )
        {
            ++ans[0];
            if( ans[ 0 ] <= 1000 )
                ans[ ans[ 0 ] ] = i;
        }
    }

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

return 0;
}