Pagini recente » Cod sursa (job #1705508) | Cod sursa (job #440939) | Cod sursa (job #438783) | Cod sursa (job #110986) | Cod sursa (job #2729245)
#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 mod=1e9 + 9;
long long hash_a=0, hash_b=0, p_n=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;
}
if(hash_a == hash_b) 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()] + b[i])%mod)%mod;
if(hash_b == hash_a) sol.push_back(i-a.size()+1);
}
out << sol.size() << '\n';
for(auto elem:sol){
out << elem << ' ';
}
out.close();
}
int main(){
read();
solve();
}