Pagini recente » Cod sursa (job #29399) | Cod sursa (job #2450683) | Cod sursa (job #1477332) | Cod sursa (job #54995) | Cod sursa (job #1193735)
#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 = 0;
prefix[0] = 0;
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 = 0;
for (int i = 0; i < n && match.size() < 1000; i++) {
// try to match
if (A[k] == B[i]) {
k ++;
} else {
while ( k > 0 && A[k] != B[i]) {
k = prefix[k];
}
}
if (k == m) {
match.push_back(i - m + 1);
k = prefix[k - 1];
}
}
}
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);
}