Pagini recente » Profil catalincraciun | Cod sursa (job #1828202) | Cod sursa (job #2502892) | Cod sursa (job #2901585) | Cod sursa (job #1193145)
#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;
vector<int> match;
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;
}
}
int count = 0;
for (int i = 0; i <= n - m ; i++) {
if (hashA == hashB_m) {
if (A.compare(B.substr(i, m)) == 0) {
match.push_back(i);
}
}
if (i + m < n)
hashB_m = (((hashB_m - (a_m * B[i]) % MOD + MOD) * D) % MOD + B[i + m]) % MOD;
}
printf("%d\n",match.size());
int nrRes = min((int) match.size(), 1000);
for (int i = 0; i < nrRes; i++) {
printf("%d ", match[i]);
}
}
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);
}