Pagini recente » Cod sursa (job #1248019) | Cod sursa (job #1742264) | Cod sursa (job #872489) | Cod sursa (job #2701331) | Cod sursa (job #1527745)
/**
Given two strings made up of letters, find all the occurrences of string A in string B.
1 <= length(A), length(B) <= 2,000,000
**/
#include <cstdio>
#include <cstring>
#include <algorithm>
#define NMAX 2000005
using namespace std;
int lengthA, lengthB;
int parent[NMAX], occurrences, printString[NMAX];
char A[NMAX], B[NMAX];
void read() {
A[0] = B[0] = '#';
scanf("%s\n%s", A + 1);
scanf("%s", B + 1);
lengthA = strlen(A) - 1;
lengthB = strlen(B) - 1;
}
void prefix() {
int q = 0;
for (int i = 2; i <= lengthA; ++i) {
parent[i] = 0;
while (q != 0 && A[i] != A[q + 1]) {
q = parent[q];
}
if (A[i] == A[q + 1]) {
q++;
}
parent[i] = q;
}
}
void kmp() {
int q = 0;
for (int i = 1; i <= lengthB; ++i) {
while (q != 0 && B[i] != A[q + 1]) {
q = parent[q];
}
if (B[i] == A[q + 1]) {
q++;
}
if (q == lengthA) {
q = parent[q];
occurrences++;
if (occurrences <= 1000) {
printString[occurrences] = i - lengthA;
}
}
}
}
void print() {
printf("%d\n", occurrences);
for (int i = 1; i <= occurrences; ++i) {
printf("%d ", printString[i]);
}
}
int main() {
read();
prefix();
kmp();
print();
}