Pagini recente » Cod sursa (job #3294753) | Cod sursa (job #424907) | Cod sursa (job #1441013) | Cod sursa (job #3031857) | Cod sursa (job #2714108)
/*
* Created by Andrei Arhire 01/03/2021
* Copyright © 2021 Andrei Arhire. All rights reserved.
* Expected verdict - Accepted
*/
#include <bits/stdc++.h>
#define pb push_back
#define zero(pos) pos&(-pos)
#define eb emplace_back
#define mp make_pair
using namespace std;
const long long NR = 2e6 + 1e2;
const long long oo = 1e16;
string s , t ;
int p1 [ NR ] , p2 [ NR ] ;
int c1 = 73 ;
int MOD1 = 1e5 + 7 , MOD2 = 1e5 + 21;
vector < int > sol ;
ifstream in ("strmatch.in") ;
ofstream out ("strmatch.out") ;
signed main() {
ios::sync_with_stdio(false);
in.tie(nullptr);
int i ;
in >> s >> t ;
if ( s.size() > t.size() ) {
cout << "0\n" ;
exit(0);
}
p1 [ 0 ] = 1 ;
p2 [ 0 ] = 1 ;
for ( i = 1 ; i <= s.size() ; ++ i ) {
p1 [ i ] = ( p1 [ i - 1 ] * c1 ) % MOD1 ;
p2 [ i ] = ( p2 [ i - 1 ] * c1 ) % MOD2 ;
}
int hash1 = 0 , hash2 = 0 ;
int hash1t = 0 , hash2t = 0 ;
for ( i = 0 ; i < s.size() ; ++ i ) {
hash1 = ( hash1 * c1 + (s[i]) ) % MOD1 ;
hash2 = ( hash2 * c1 + (s[i] ) ) % MOD2 ;
hash1t = ( hash1t * c1 + (t[i]) ) % MOD1 ;
hash2t = ( hash2t * c1 + (t[i] ) ) % MOD2 ;
}
if ( hash1 == hash1t && hash2 == hash2t ) {
sol.pb( 0 ) ;
}
for ( i = s.size() ; i < t.size() ; ++ i ){
hash1t = ( (hash1t - p1 [ s.size() - 1 ] * (t[i-s.size()]) %MOD1 + MOD1)%MOD1 ) * c1 % MOD1 + (t[i] ) ;
hash1t = ( (hash2t - p2 [ s.size() - 1 ] * (t[i-s.size()]) %MOD2 + MOD2)%MOD2 ) * c1 % MOD2 + (t[i] ) ;
if ( hash1 == hash1t && hash2 == hash2t ) {
sol.pb( i - s.size() + 1 ) ;
}
}
out << sol.size() << '\n' ;
for ( i = 0 ; i < min ( 1000,(int) sol.size() ) ; ++ i ) {
out << sol [ i ] << ' ' ;
}
out << '\n' ;
return 0;
}