Pagini recente » Cod sursa (job #3158960) | Cod sursa (job #1327138) | Cod sursa (job #2808570) | Cod sursa (job #3178438) | Cod sursa (job #2729219)
#include <bits/stdc++.h>
using namespace std;
const unsigned int p = 31;
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]
// hash[i] = hash[i-1]*p + a[n+i] - p^(n+1)*a[i-1];
void read(){
cin >> a;
cin >> b;
}
void solve(){
unsigned int hash_a=0, hash_b=0, p_n=1;
for(unsigned int i=0; i<a.size(); i++){
hash_a = hash_a*p + a[i];
hash_b = hash_b*p + b[i];
p_n*=p;
}
vector<int> sol;
if(hash_a == hash_b){
sol.push_back(0);
}
for(unsigned int i=a.size(); i<b.size() && sol.size()<1000; i++){
hash_b = hash_b*p + b[i] - b[i-a.size()]*p_n;
if(hash_a == hash_b){
sol.push_back(i-a.size()+1);
}
}
cout << sol.size() << '\n';
for(auto elem:sol){
cout << elem << ' ';
}
}
int main(){
read();
solve();
}