Pagini recente » Cod sursa (job #1266301) | Cod sursa (job #727069) | Cod sursa (job #1012095) | Cod sursa (job #392471) | Cod sursa (job #2631758)
#include <fstream>
#include <string>
#include <vector>
#include <list>
using namespace std;
const int MAX_NO_POS = 1000;
const int BASE = 62;
const int MOD = 10007;
void rabinKarp(string & A, string & B, int & n, list<int> & ans) {
if (A.size() > B.size()) {
return;
}
int hashWindow = 0;
int hashPattern = 0;
int pow = 1;
for (int i = 0; i < A.size() - 1; i++) {
pow = (pow * BASE) % MOD;
}
for (int i = 0; i < A.size(); i++) {
hashWindow = (BASE * hashWindow + B[i]) % MOD;
hashPattern = (BASE * hashPattern + A[i]) % MOD;
}
if (hashWindow == hashPattern && A == B.substr(0, A.size())) {
n++;
ans.push_back(0);
}
for (int i = A.size(); i < B.size(); i++) {
hashWindow = (BASE * (hashWindow - (pow * B[i - A.size()])) + B[i]) % MOD;
hashWindow += (hashWindow < 0) ? MOD : 0;
if (hashWindow == hashPattern && A == B.substr(i - A.size() + 1, A.size())) {
n++;
if (n <= MAX_NO_POS) {
ans.push_back(i - A.size() + 1);
}
}
}
}
int main() {
ifstream fin;
ofstream fout;
string A, B;
fin.open("strmatch.in");
fin >> A >> B;
fin.close();
int n = 0;
list<int> ans;
rabinKarp(A, B, n, ans);
fout.open("strmatch.out");
fout << n << endl;
for (auto it = ans.begin(); it != ans.end(); ++it) {
fout << *it << " ";
}
fout.close();
ans.clear();
return 0;
}