Pagini recente » Cod sursa (job #2543538) | Cod sursa (job #2642442) | Cod sursa (job #611692) | Cod sursa (job #1095809) | Cod sursa (job #1193138)
#include <iostream>
#include <stdio.h>
#include <string>
#include <vector>
#include <algorithm>
#include <string.h>
#define MAXN 2000001
#define MOD 100007
#define D 'z'
using namespace std;
bool match[MAXN];
void rabinKarpMatch(string A, string B) {
int m = A.length();
int n = B.length();
int a_m = 1;
int hashA = 0, hashB_m = 0;
for (int i = 0; i < m; i++) {
hashA = ((hashA * D) % MOD + A[i]) % MOD;
hashB_m = ((hashB_m * D) % MOD + B[i]) % MOD;
if (i != 0) {
a_m = (a_m * D) % MOD;
}
}
memset(match, 0, sizeof (bool) * MAXN);
int count = 0;
for (int i = 0; i <= n - m - 1; i++) {
if (hashA == hashB_m) {
if (A.compare(B.substr(i, m)) == 0) {
match[i] = true;
count++;
}
}
if (i + m < n)
hashB_m = (((hashB_m - (a_m * B[i]) % MOD + MOD) * D) % MOD + B[i + m]) % MOD;
}
cout << count << endl;
int nrRes = min((int) count, 1000);
for (int i = 0; i < MAXN || nrRes > 0; i++) {
if (match[i]) {
cout << i<< " ";
nrRes --;
}
}
}
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
string A, B;
cin >> A >> B;
rabinKarpMatch(A, B);
fclose(stdin);
fclose(stdout);
}