Pagini recente » Cod sursa (job #3041331) | Cod sursa (job #648380) | Cod sursa (job #2360414) | carburanti | Cod sursa (job #1113631)
#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 )
{
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 )
{
vect.push_back(i) ; cnt ++ ;
}
}
out << cnt << "\n" ;
for ( std::vector<int>::iterator it = vect.begin() ; it != vect.end() ; it ++ )
{
out << *it << " " ;
}
return 0;
}