Pagini recente » Cod sursa (job #2347432) | Cod sursa (job #829892) | Cod sursa (job #620672) | Cod sursa (job #240741) | Cod sursa (job #2470562)
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define NMAX 1000
#define BUFFER_SIZE 1 << 17
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
char pattern[BUFFER_SIZE], string[BUFFER_SIZE];
scanf("%s%s", pattern, string);
int len_pattern = strlen(pattern);
int len_string = strlen(string) - 1;
if (len_pattern > len_string) {
fprintf(stderr, "Gigele, nu-i de bine...\n");
goto error;
}
int i = 1, j = 0, count = 0;
int *pi = calloc(len_pattern, sizeof(*pi));
int *position = calloc(NMAX, sizeof(*position));
build_pref_array:
if (i == len_pattern) {
goto KMP;
}
back_pref_array:
if (j && pattern[i] != pattern[j]) {
j = pi[j - 1];
goto back_pref_array;
}
if (pattern[i] == pattern[j]) {
++j;
}
pi[i] = j;
++i;
goto build_pref_array;
KMP:
i = 0, j = 0;
search:
if (i == len_string) {
goto print;
}
match:
if (j && pattern[j] != string[i]) {
j = pi[j - 1];
goto match;
}
if (pattern[j] == string[i]) {
++j;
}
if (j == len_pattern) {
position[count++] = i - len_pattern + 1;
j = pi[j - 1];
}
++i;
goto search;
print:
printf("%d\n", count);
i = 0;
print_position:
if (i < count) {
printf("%d ", position[i]);
++i;
goto print_position;
}
printf("\n");
error:
free(pi);
free(position);
fclose(stdin);
return 0;
}