Pagini recente » Cod sursa (job #1985408) | Cod sursa (job #2376452) | Cod sursa (job #411102) | Cod sursa (job #2502516) | Cod sursa (job #3242815)
#include <bits/stdc++.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
const int NMAX = 2e6;
const int B = 31;
const int 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] - 'A' + 1) * putere[i]) % MOD;
}
//hash-ul pentru text
ht[0] = (t[0] - 'A' + 1);
for(int i = 1; i < t.size(); i++) {
ht[i] = (ht[i - 1] + (t[i] - 'A' + 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) {
sol.push_back(i);
if(sol.size() >= 1000) {
break;
}
//cout << i << ' ';
}
}
g << sol.size() << '\n';
for(int i = 0; i < sol.size(); i++) {
g << sol[i] << ' ';
}
return 0;
}