Pagini recente » Cod sursa (job #2274253) | Cod sursa (job #2587860) | Cod sursa (job #1721183) | Cod sursa (job #2322643) | Cod sursa (job #1130818)
#include<fstream>
#include<vector>
#include<string.h>
using namespace std;
#define max_n 2000010
#define base 73
#define mod1 100007
#define mod2 100021
#define s_max 1000
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int L , LB , p1 , p2;
int hashA1 , hashA2 , hashB1 , hashB2;
char s1[max_n] , s2[max_n];
vector<int>Sol;
void read(){
f>>s1>>s2;
L = strlen(s1);
LB = strlen(s2);
}
int power( int a , int b , int mod ){
if( b == 0 )
return 1;
int p = power(a , b / 2 , mod);
if( b % 2 == 1 )
return (((p * p) % mod) * a) % mod;
else
return (p * p) % mod;
}
int main(){
read();
if( L > LB )
goto end;
p1 = power(base , L - 1 , mod1);
p2 = power(base , L - 1 , mod2);
for( int i = 0 ; i < L ; i++ ){
hashA1 = (hashA1 * base + s1[i]) % mod1;
hashA2 = (hashA2 * base + s1[i]) % mod2;
}
for( int i = 0 ; i < L ; i++ ){
hashB1 = (hashB1 * base + s2[i]) % mod1;
hashB2 = (hashB2 * base + s2[i]) % mod2;
}
if( hashB1 == hashA1 && hashB2 == hashA2 )
Sol.push_back(0);
for( int i = L ; i < LB ; i++ ){
hashB1 = (((( hashB1 - p1 * s2[i-L] ) % mod1) + mod1) * base + s2[i]) % mod1;
hashB2 = (((( hashB2 - p2 * s2[i-L] ) % mod2) + mod2) * base + s2[i]) % mod2;
if( hashB1 == hashA1 && hashB2 == hashA2 )
Sol.push_back(i - L + 1);
if( Sol.size() == s_max )
break;
}
end:
g<<Sol.size()<<"\n";
for( unsigned int i = 0 ; i < Sol.size() ; i++ )
g<<Sol[i]<<" ";
return 0;
}