Pagini recente » Cod sursa (job #1026401) | Cod sursa (job #1707892) | Cod sursa (job #1087867) | Cod sursa (job #1073572) | Cod sursa (job #1193750)
#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;
int prefix[MAXN];
vector<int> match;
void computePrefix(string A) {
int m = A.length();
int k = -1;
prefix[0] = -1;
for (int i = 1; i < m; i++) {
while (k > 0 && A[k + 1] != A[i]) {
k = prefix[k];
}
if (A[k + 1] == A[i]) {
k = k + 1;
}
prefix[i] = k;
}
}
void kmp(string A, string B) {
computePrefix(A);
int m = A.length();
int n = B.length();
int k = -1;
for (int i = 0; i < n; i++) {
// try to match
while (k >= 0 && A[k + 1] != B[i]) {
k = prefix[k];
}
if (A[k + 1] == B[i]) {
k++;
}
if (k == m - 1) {
match.push_back(i - m + 1);
k = prefix[k];
}
}
}
void print() {
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;
kmp(A, B);
print();
fclose(stdin);
fclose(stdout);
}