Pagini recente » Cod sursa (job #21642) | Cod sursa (job #1631441) | Cod sursa (job #926950) | Clasament nouadetrefla | Cod sursa (job #1472986)
#include <stdio.h>
#include <string.h>
#define MAX_LEN 2000000
#define MAX_POS 1000
int pos[MAX_POS];
char a[MAX_LEN + 2];
char b[MAX_LEN + 2];
int pi[MAX_LEN]; // pi[i] = lungimea celui mai lung prefix al S[1..i]
// care este si sufix al S[1..i]
void buildPrefix(char *s, int length) {
int q = 0;
pi[0] = 0;
for (int i = 1; i < length; i++) {
while ((q > 0) && (s[i] != s[q])) {
q = pi[q - 1];
}
if (s[q] == s[i]) {
q++;
}
pi[i] = q;
}
}
int main(void) {
int n, m;
int q;
int ans;
FILE *f = fopen("strmatch.in", "r");
fgets(a, MAX_LEN + 2, f);
fgets(b, MAX_LEN + 2, f);
fclose(f);
n = strlen(a) - 1;
m = strlen(b) - 1;
buildPrefix(a, n);
q = 0;
ans = 0;
for (int i = 0; i < m; i++) {
while ((q > 0) && (a[q] != b[i])) {
q = pi[q - 1];
}
if (a[q] == b[i]) {
q++;
}
if (q == n) {
if (ans < MAX_POS) {
pos[ans] = i;
}
ans++;
}
}
f = fopen("strmatch.out", "w");
fprintf(f, "%d\n", ans);
if (ans > MAX_POS) {
ans = MAX_POS;
}
for (int i = 0; i < ans; i++) {
fprintf(f, "%d ", pos[i] - n + 1);
}
fclose(f);
return 0;
}