Pagini recente » Cod sursa (job #2163528) | Cod sursa (job #2076726) | Cod sursa (job #3221694) | Cod sursa (job #1966733) | Cod sursa (job #2976988)
// sursa cu rabin-karp
#include <fstream>
#include <climits>
#include <cstring>
#include <vector>
#define d 73 // baza
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char a[2000005], b[2000005];
vector<int> ans;
int main() {
fin >> a >> b;
if(a > b) {
fout << "0";
return 0;
}
int MOD = INT_MAX;
int m = strlen(a), n = strlen(b);
int hA = 0, hB = 0; // hash-ul pt a, respectiv hash-ul pt b
int h = 1;
for(int i = 0; i < m - 1; i++) {
h = (h * d) % MOD;
}
for(int i = 0; i < m; i++) {
hA = (d * hA + a[i]) % MOD;
hB = (d * hB + b[i]) % MOD;
}
for(int i = 0; i <= n - m; i++) {
if(hA == hB) {
ans.push_back(i);
if(ans.size() == 1000) {
break;
}
}
if(i < n - m) {
hB = (d * (hB - b[i] * h) + b[i + m]) % MOD;
if(hB < 0) {
hB = (hB + MOD);
}
}
}
fout << ans.size() << "\n";
for(auto i : ans) {
fout << i << " ";
}
return 0;
}