Pagini recente » Cod sursa (job #3285631) | Cod sursa (job #1097109) | Cod sursa (job #278003) | Cod sursa (job #1170633) | Cod sursa (job #2453911)
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <unordered_map>
using namespace std;
class rolling_hash{
private:
int base;
int mod;
int len;
int h;
int pwr;
public:
rolling_hash(int base, int mod, int len): base{base}, mod{mod}, len{len}{
pwr = 1;
for (int i = 1; i <= len - 1; i++){
pwr = (pwr * base) % mod;
}
h = 0;
}
void add(char c){
h = (h * base + c) % mod;
}
void remove(char c){
h = (h - (pwr * c) % mod + mod) % mod;
}
int get_hash(){
return h;
}
};
int main() {
ios_base::sync_with_stdio(false);
ifstream in("data.txt");
ofstream out("strmatch.out");
string a, b;
in >> a >> b;
if (a.size() > b.size()){
cout << "0\n";
return 0;
}
rolling_hash h1_a(91, 666013, a.size());
rolling_hash h2_a(97, 666013, a.size());
for (char c: a){
h1_a.add(c);
h2_a.add(c);
}
rolling_hash h1_b(91, 666013, a.size());
rolling_hash h2_b(97, 666013, a.size());
for (size_t i = 0; i < a.size() - 1; i++){
h1_b.add(b[i]);
h2_b.add(b[i]);
}
vector<int> matches;
for (size_t i = a.size() - 1; i < b.size(); i++){
h1_b.add(b[i]);
h2_b.add(b[i]);
if (h1_a.get_hash() == h1_b.get_hash()){
matches.push_back(i);
}
h1_b.remove(b[i - a.size() + 1]);
h2_b.remove(b[i - a.size() + 1]);
}
out << matches.size() << endl;
for (int x: matches){
out << x - a.size() + 1 << " " ;
}
out << endl;
return 0;
}