Cod sursa(job #1113627)

Utilizator techLaurentiu Avasiloaie tech Data 20 februarie 2014 19:36:43
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include <fstream>
#include <vector>
#include <string.h>
#define MODULO 1000000007
#define BASE 257

using namespace std;

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

char sub[2000005] , sir[2000005] ;
long long int sub_length , sir_length , hash_sub, hash_sir , i , power = 1 , cnt ;

std::vector<int> vect ;

int main()
{
    in >> sub >> sir ;

    sub_length = strlen(sub) ; sir_length = strlen(sir) ;

    power = 1 ;

    for ( i = 0 ; i < sub_length ; i ++ )
    {
        hash_sub = ( hash_sub * BASE + sub[i] ) % MODULO ;
        hash_sir = ( hash_sir * BASE + sir[i] ) % MODULO ;
        power = ( power * BASE ) % MODULO ;
    }

    if ( hash_sub == hash_sir )
    {
        if ( strncmp ( sub , sir , sub_length ) == 0 )
        {
            vect.push_back(0) ;
        }
    }

    for ( i = 1 ; i < sir_length - sub_length ; i ++ )
    {
        hash_sir = ( ( hash_sir * BASE + sir[i+sub_length-1] ) % MODULO ) ;
        hash_sir -= ( ( sir[i-1] * power ) % MODULO ) ;

        if ( hash_sir < 0 ) { hash_sir += MODULO ; }

        if ( hash_sub == hash_sir )
        {
            if ( strncmp ( sub , sir+i , sub_length ) == 0 )
            {
                vect.push_back(i) ; cnt ++ ;
            }
        }
    }

    out << cnt << "\n" ;

    for ( std::vector<int>::iterator it = vect.begin() ; it != vect.end() ; it ++ )
    {
        out << *it << " " ;
    }

    return 0;
}