Pagini recente » Cod sursa (job #1597227) | Cod sursa (job #1635925) | Cod sursa (job #301511) | Cod sursa (job #2581947) | Cod sursa (job #2641277)
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define lll long long
#define llf __float128
#define lld long double
using namespace std;
const int NR = 2e6 + 10 ,oo = 2e9 + 10, MOD1 = 1e9 + 7 , MOD2 = 1e9 + 9 ;
const long double pi = 2*acos(0.0);
string s1 , s2 ;
int fact1 [ NR ] , fact2 [ NR ] , temp1 , temp2 , cnt , temp10 , temp20 ;
vector < int > sol ;
ifstream in ("strmatch.in") ;
ofstream out ("strmatch.out") ;
signed main () {
int i , hash1 = 0 , j , hash2 = 0 ;
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0) ;
in >> s1 >> s2 ;
fact1 [ 0 ] = 1 ;
fact2 [ 0 ] = 1 ;
for ( i = 1 ; i <= s2.size() ; ++ i ) {
fact1 [ i ] = 1LL * fact1 [ i - 1 ] * 1000003 % MOD1 ;
fact2 [ i ] = 1LL * fact2 [ i - 1 ] * 1000033 % MOD2 ;
}
for ( i = 0 ; i < s1.size() ; ++ i ) {
hash1 = 1LL * ( hash1 + 1LL * fact1 [ i + 1 ] * ( s1 [ i ] - 'A' + 1 ) % MOD1 ) % MOD1 ;
hash2 = 1LL * ( hash2 + 1LL * fact2 [ i + 1 ] * ( s1 [ i ] - 'A' + 1 ) % MOD2 ) % MOD2 ;
}
hash1 = 1LL * hash1 * fact1 [ s2.size() - s1.size() ] % MOD1 ;
hash2 = 1LL * hash2 * fact2 [ s2.size() - s1.size() ] % MOD2 ;
for ( i = 0 ; i < s1.size() ; ++ i ) {
temp1 = 1LL * ( temp1 + 1LL * fact1 [ i + 1 ] * ( s2 [ i ] - 'A' + 1 ) % MOD1 ) % MOD1 ;
temp2 = 1LL * ( temp2 + 1LL * fact2 [ i + 1 ] * ( s2 [ i ] - 'A' + 1 ) % MOD2 ) % MOD2 ;
}
temp10 = 1LL * temp1 * fact1 [ s2.size() - i ] % MOD1 ;
temp20 = 1LL * temp2 * fact2 [ s2.size() - i ] % MOD2 ;
if ( temp10 == hash1 && temp20 == hash2 ) {
++ cnt ;
if ( cnt <= 1000 )
sol.pb(i-s1.size()) ;
}
for ( ; i < s2.size() ; ++ i ) {
temp1 = 1LL * ( temp1 + 1LL * fact1 [ i + 1 ] * ( s2 [ i ] - 'A' + 1 ) % MOD1 ) % MOD1 ;
temp2 = 1LL * ( temp2 + 1LL * fact2 [ i + 1 ] * ( s2 [ i ] - 'A' + 1 ) % MOD2 ) % MOD2 ;
temp1 = 1LL * ( temp1 - 1LL * fact1 [ i + 1 - s1.size() ] * ( s2 [ i - s1.size() ] - 'A' + 1 ) % MOD1 + MOD1 ) % MOD1 ;
temp2 = 1LL * ( temp2 - 1LL * fact2 [ i + 1 - s1.size() ] * ( s2 [ i - s1.size() ] - 'A' + 1 ) % MOD2 + MOD2 ) % MOD2 ;
temp10 = 1LL * temp1 * fact1 [ s2.size() - i - 1 ] % MOD1 ;
temp20 = 1LL * temp2 * fact2 [ s2.size() - i - 1 ] % MOD2 ;
if ( temp10 == hash1 && temp20 == hash2 ) {
++ cnt ;
if ( cnt <= 1000 )
sol.pb(i-s1.size()+1) ;
}
}
out << cnt << '\n' ;
for ( auto it : sol ) out << it << ' ' ;
return 0 ;
}