Cod sursa(job #1113621)

Utilizator techLaurentiu Avasiloaie tech Data 20 februarie 2014 19:29:17
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 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 ;

std::vector<int> vect ;

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

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

    for ( i = 0 ; i < sub_length ; i ++ )
    {
        hash_sub = ( hash_sub + sub[i] )  ;
        hash_sir = ( hash_sir + sir[i] )  ;
    }

    /*power = 1 ;

    for ( i = 0 ; i < sub_length ; i ++ )
    {
        power = ( power * BASE )  ;
    }*/

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

    //out << sub_length << " " << sir_length << " " << power << " " << hash_sub << " " << hash_sir << endl ;

    for ( i = 1 ; i < sir_length - sub_length ; i ++ )
    {
        hash_sir = ( ( hash_sir + sir[i] )  ) ;
        hash_sir -= ( sir[i-1] ) ;

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

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

    out << vect.size() << "\n" ;

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

    return 0;
}