Pagini recente » Cod sursa (job #2229323) | Cod sursa (job #384391) | Cod sursa (job #1765677) | Cod sursa (job #1209839) | Cod sursa (job #2080620)
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
using namespace std;
ifstream f ("strmatch.in");
ofstream g ("strmatch.out");
const int B = 127;
const int NMAX = 2000000;
int n, m;
char a[NMAX + 1];
char b[NMAX + 1];
vector <int> sol;
void citeste() {
f >> a >> b;
n = strlen(a);
m = strlen(b);
}
unsigned long long get_hash(int n, char *s) {
unsigned long long h = 0;
unsigned long long b = 1;
for (int i = 0; i < n; i++) {
h = h + b * s[i];
b = b * B;
}
return h;
}
void unhash(unsigned long long h) {
char c = 0;
while(h) {
c = h % 127;
h = h / 127;
cout << c;
}
cout << endl;
}
void rolling_hash() {
unsigned long long h = get_hash(n, a);
unsigned long long current_h = get_hash(n, b);
unsigned long long b_ = 1;
for (int i = 1; i < n; i++) b_ = b_ * B;
if (current_h == h) sol.push_back(0);
for (int i = n; i < m; i++) {
current_h = current_h / B + b_ * b[i];
if (current_h == h) sol.push_back(i - n + 1);
if (sol.size() > 1000) return;
}
}
void scrie() {
int l = sol.size();
g << l << '\n';
for (int i = 0; i < l; i++)
g << sol[i] << ' ';
g << '\n';
}
int main() {
citeste();
rolling_hash();
scrie();
return 0;
}