Pagini recente » Cod sursa (job #3289026) | Cod sursa (job #563637) | Cod sursa (job #2926185) | Cod sursa (job #2397384) | Cod sursa (job #2977425)
// sursa cu rabin-karp
#include <fstream>
#include <cstring>
#define MOD1 100007
#define MOD2 100021
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char a[2000005], b[2000005];
int ans[1005];
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;
}
}
int nr = 0;
if(hA1 == hB1 && hA2 == hB2) {
nr++;
ans[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[nr] = (i - n + 1);
}
}
}
fout << nr << "\n";
for(int i = 1; i <= min(nr, 1000); i++) {
fout << ans[i] << " ";
}
return 0;
}