Pagini recente » Cod sursa (job #2978182) | Cod sursa (job #472887) | Cod sursa (job #217573) | Cod sursa (job #2859345) | Cod sursa (job #2729224)
#include <bits/stdc++.h>
using namespace std;
const unsigned long long p = 31;
const unsigned long long p2 = 6553;
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(){
ifstream in("strmatch.in");
in >> a;
in >> b;
in.close();
}
void solve(){
ofstream out("strmatch.out");
unsigned long long hash_a=0, hash_b=0, p_n=1;
unsigned long long hash_a2=0, hash_b2=0, p_n2=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;
hash_a2 = hash_a2*p2 + a[i];
hash_b2 = hash_b2*p2 + b[i];
p_n2*=p2;
}
vector<int> sol;
if(hash_a == hash_b && hash_a2 == hash_b2){
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;
hash_b2 = hash_b2*p2 + b[i] - b[i-a.size()]*p_n2;
if(hash_a == hash_b && 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();
}