Pagini recente » Cod sursa (job #989809) | Cod sursa (job #3219059) | Cod sursa (job #1396504) | Cod sursa (job #2056252) | Cod sursa (job #2333567)
#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);
if(N>M)
{
printf("0");
return;
}
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++,sol1.push_back(0);
for (int i = N; i < M; i++) {
BM1 = ((BM1 - ((B[i - N] * P1) % MOD1) + MOD1) * P + B[i]) % MOD1;
BM2 = ((BM2 - ((B[i - N] * P2) % 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;
}