Pagini recente » Cod sursa (job #3181089) | Cod sursa (job #378556) | Cod sursa (job #2390284) | Cod sursa (job #2638987) | Cod sursa (job #3242819)
#include <bits/stdc++.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
const int NMAX = 2e6;
const long long B = 127;
const long long MOD = 1e9 + 7;
long long putere[NMAX + 1];
long long ht[NMAX + 1];
int main() {
string p;
string t;
f >> p >> t;
putere[0] = 1;
for(int i = 1; i < max(p.size(), t.size()); i++) {
putere[i] = (putere[i - 1] * B) % MOD;
}
//hash-ul pentru pattern
long long hp = 0;
for(int i = 0; i < p.size(); i++) {
hp = (hp + (p[i] - '0' + 1) * putere[i]) % MOD;
}
//hash-ul pentru text
ht[0] = (t[0] - '0' + 1);
for(int i = 1; i < t.size(); i++) {
ht[i] = (ht[i - 1] + (t[i] - '0' + 1) * putere[i]) % MOD;
}
int sz = p.size();
vector<int> sol;
for(int i = 0; i + sz - 1 < t.size(); i++) {
long long h;
if(i == 0) {
h = ht[i + sz - 1];
} else {
h = (ht[i + sz - 1] - ht[i - 1] + MOD) % MOD;
}
if(h == (hp * putere[i]) % MOD) {
if(sol.size() < 1000) {
sol.push_back(i);
}
//cout << i << ' ';
}
}
g << sol.size() << '\n';
for(int i = 0; i < sol.size(); i++) {
g << sol[i] << ' ';
}
return 0;
}