Pagini recente » Cod sursa (job #392271) | Cod sursa (job #161513) | Cod sursa (job #634563) | Cod sursa (job #1035333) | Cod sursa (job #2218844)
#include <stdio.h>
#include <string.h>
#define SIZE 2000000
char A[SIZE], B[SIZE];
int prefix[SIZE];
int sol[SIZE];
int matches;
void build_prefix() {
int length = strlen(A);
int index = 0;
for(int i = 1; i < length;) {
if (A[index] == A[i]) {
index += 1;
prefix[i] = index;
i += 1;
}
else {
if (index != 0)
index = prefix[index - 1];
else {
prefix[i] = 0;
i += 1;
}
}
}
}
void KMP() {
int pattern_index = 0;
int text_index = 0;
int pattern_size = strlen(A);
int text_size = strlen(B);
pattern_index = text_index = 0;
while (text_index < text_size) {
if (B[text_index] == A[pattern_index]) {
text_index++;
pattern_index++;
if (pattern_index == pattern_size) {
pattern_index = prefix[pattern_size - 1];
sol[matches] = text_index - pattern_size;
matches += 1;
}
} else {
if (pattern_index != 0)
pattern_index = prefix[pattern_index - 1];
else {
text_index++;
}
}
}
}
int main(void) {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s", A);
scanf("%s", B);
build_prefix();
KMP();
printf("%d\n", matches);
if (matches > 1000)
matches = 1000;
for (int i = 0; i < matches; ++i)
printf("%d ", sol[i]);
printf("\n");
}