Cod sursa(job #1542329)

Utilizator andrei_bB. Andrei andrei_b Data 5 decembrie 2015 12:09:30
Problema Potrivirea sirurilor Scor 8
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <fstream>
#include <cstring>

using namespace std;

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

int z[2000005],sol[2000005],st,dr,cate,sir,nr,este;
char s[2000005],v[2000005];

int minim ( int a , int b ){

    if ( a > b )
        return a;
    return b;
}

int main()
{
    fin.getline( s , 2000005 );
    cate=strlen(s);
    fin.getline( v , 2000005 );
    s[cate+1]='*';
    strcat( s , "*" );
    strcat( s , v );
    st=-1;
    dr=-1;
    nr=strlen(s);
    for ( int i=1 ; i<=nr-1 ; i++ ){
        if ( i <= dr )
            z[i]=minim(dr-i+1,z[i-st]);
        while ( s[z[i]]==s[i+z[i]] )
            z[i]=z[i]+1;
        if ( i+z[i]-1 > dr ){
            dr=i+z[i]-1;
            st=i;
        }
    }
    for ( int i=0 ; i<=nr-1 ; i++ ){
        if ( z[i]==cate ){
            sol[i]=1;
            este++;
        }
    }
    fout<<este<<'\n';
    for ( int i=1 ; i<=nr-1 ; i++ ){
        if ( sol[i]==1 )
            fout<<i-cate-1<<' ';
    }
}