Pagini recente » Cod sursa (job #2462388) | Cod sursa (job #580777) | Cod sursa (job #2623276) | Cod sursa (job #2870479) | Cod sursa (job #2977423)
// sursa cu rabin-karp
#include <fstream>
#include <cstring>
#include <vector>
#define MOD1 100007
#define MOD2 100021
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 n = strlen(a), m = strlen(b);
int hA1 = 0, hA2 = 0, hB1 = 0, hB2 = 0; // hash-uri pt a, respectiv hash-uri pt b
int h1 = 1, h2 = 1;
for(int i = 0; i < n; i++) {
hA1 = (73 * hA1 + a[i]) % MOD1;
hA2 = (73 * hA2 + a[i]) % MOD2;
hB1 = (73 * hB1 + b[i]) % MOD1;
hB2 = (73 * hB2 + b[i]) % MOD2;
if(i != 0) {
h1 = (h1 * 73) % MOD1;
h2 = (h2 * 73) % MOD2;
}
}
if(hA1 == hB1 && hA2 == hB2) {
ans.push_back(0);
}
int nr = 0;
for(int i = n; i < m; i++) {
hB1 = ((hB1 - (b[i - n] * h1) % MOD1 + MOD1) * 73 + b[i]) % MOD1;
hB2 = ((hB2 - (b[i - n] * h2) % MOD2 + MOD2) * 73 + b[i]) % MOD2;
if(hA1 == hB1 && hA2 == hB2) {
nr++;
if(nr <= 1000) {
ans.push_back(i - n + 1);
}
}
}
fout << nr << "\n";
for(auto i : ans) {
fout << i << " ";
}
return 0;
}