Pagini recente » Cod sursa (job #3234221) | Cod sursa (job #279605) | Cod sursa (job #990707) | Cod sursa (job #2590027) | Cod sursa (job #2333557)
#include<cstdio>
#include <vector>
#include <cstring>
/* #include "Euclid.cpp"
#include "EuclidExtended.cpp"
#include "LCS.cpp"
#include "RabinKarp.cpp" */
using namespace std;
class RabinKarp {
#define NMAX 2000000+3
#define P 73
#define MOD1 100007
#define MOD2 100021
private:
char A[NMAX], B[NMAX];
int AM1, AM2;
int P1, P2;
int N, M;
vector<int> sol1;
void precalc() {
P1 = 1;
P2 = 1;
for (int i = 0; i <= N - 1; i++) {
AM1 = (AM1 * P + A[i]) % MOD1;
AM2 = (AM2 * P + A[i]) % MOD2;
if (i) {
P1 = (P1 * P) % MOD1;
P2 = (P2 * P) % MOD2;
}
}
}
public:
void rabinKarp_main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s %s", A, B);
int sol = 0;
N = strlen(A);
M = strlen(B);
precalc();
long BM1 = 0, BM2 = 0;
for (int i = 0; i <= N - 1; i++) {
BM1 = (BM1 * P + B[i]) %MOD1;
BM2 = (BM2 * P + B[i]) %MOD2;
}
if (BM1 == AM1 && BM2 == AM2)
sol++;
for (int i = N; i <= M - 1; i++) {
BM1 = (((BM1 - ((B[i - N] * P1) % MOD1) + MOD1) % MOD1) * P + B[i]) % MOD1;
BM2 = (((BM2 - ((B[i - N] * P2) % MOD2) + MOD2) % MOD2) * P + B[i]) % MOD2;
if (BM1 == AM1 && BM2 == AM2)
sol++, sol1.push_back(i-N+1);
}
printf("%d\n", sol);
for (auto &i:sol1) {
printf("%d ", i);
}
}
} rabinKarp;
int main()
{
rabinKarp.rabinKarp_main();
return 0;
}