Pagini recente » Cod sursa (job #1168125) | Cod sursa (job #1831112) | Cod sursa (job #2715202) | Cod sursa (job #2500358) | Cod sursa (job #2729255)
#include <bits/stdc++.h>
using namespace std;
string a,b;
// use unsigned for easy modulo
// hash[0] = (a[0]*p^n + a[1]*p^(n-1) + ... + a[n-1]*p + a[n])%mod
// hash[i] = hash[i-1]*p + a[n+i] - p^(n+1)*a[i-1];
void read(){
ifstream in("strmatch.in");
in >> a;
in >> b;
in.close();
}
void solve(){
ofstream out("strmatch.out");
const int p=31;
const int p2=73;
const int mod=1e9 + 9;
const int mod2=1e9 + 7;
long long hash_a=0, hash_b=0, p_n=1;
long long hash_a2=0, hash_b2=0, p_n2=1;
vector<int> sol;
for(unsigned int i=0; i<a.size(); i++){
hash_a = (hash_a*p + a[i])%mod;
hash_b = (hash_b*p + b[i])%mod;
p_n=p_n*p%mod;
hash_a2 = (hash_a2*p2 + a[i])%mod2;
hash_b2 = (hash_b2*p2 + b[i])%mod2;
p_n2=p_n2*p2%mod2;
}
if(hash_a == hash_b && hash_b2 == hash_a2) sol.push_back(0);
for(unsigned int i=a.size(); i<b.size() && sol.size()<1000; i++){
hash_b = (mod + hash_b*p - p_n*b[i-a.size()]%mod + b[i])%mod;
hash_b2 = (mod2 + hash_b2*p2 - p_n2*b[i-a.size()]%mod2 + b[i])%mod2;
if(hash_b == hash_a && hash_a2 == hash_b2) sol.push_back(i-a.size()+1);
}
out << sol.size() << '\n';
for(auto elem:sol){
out << elem << ' ';
}
out.close();
}
int main(){
read();
solve();
}