Pagini recente » Cod sursa (job #1686194) | Cod sursa (job #867777) | Cod sursa (job #2931950) | Cod sursa (job #2529133) | Cod sursa (job #2668772)
#include <bits/stdc++.h>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string pat, txt;
const int d = 256, mod = 2000003;
set<int> sol;
void rabin_karp(string pat, string txt, int q) {
int p = 0, t = 0, h = 1, j = 0;
int m = pat.size();
int n = txt.size();
for(int i = 0; i < m - 1; ++i) {
h = (h * d) % q;
}
for(int i = 0; i < m; ++i) {
p = (d * p + pat[i]) % q;
t = (d * t + txt[i]) % q;
}
for(int i = 0; i <= n - m; ++i) {
if(p == t) {
for(j = 0; j < m; ++j) {
if(txt[i+j] != pat[j]) {
break;
}
}
if(j == m) {
sol.insert(i);
}
}
if(i < n - m) {
t = (d * (t - txt[i]*h) + txt[i+m]) % q;
if(t < 0) {
t = (t+q);
}
}
}
}
void read() {
getline(f, pat);
// f.get();
getline(f, txt);
}
void solve() {
read();
rabin_karp(pat, txt, mod);
g << sol.size() << '\n';
for(int val : sol) {
g << val << " ";
}
g << '\n';
}
int main(void) {
solve();
}