Pagini recente » Cod sursa (job #1769883) | Cod sursa (job #1180924) | Cod sursa (job #879259) | Cod sursa (job #956445) | Cod sursa (job #1472775)
/*
* Z[i] = lungimea celui mai lungi subsecvente incepand cu B[i]
* care este si prefix al lui A
*/
#include <stdio.h>
#include <string.h>
#define MAX_LEN 2000000
#define MAX_POS 1000
char A[2 * MAX_LEN + 1];
int Z[2 * MAX_LEN];
int pos[MAX_POS];
inline int MIN(int X, int Y) {
return X < Y ? X : Y;
}
void process(char *A, int length) {
int l = 0, r = 0;
for (int i = 1; i < length; i++) {
// [l, r] este segmentul curent
if (i <= r) { // i face parte din segmentul curent
// Z[i - l] ar putea depasi R, dar nu stim ce e in dreapta lui R
Z[i] = MIN(r - i + 1, Z[i - l]);
}
while (i + Z[i] < length && A[Z[i]] == A[i + Z[i]]) {
Z[i]++;
}
if (i + Z[i] - 1 > r) {
l = i;
r = i + Z[i] - 1;
}
}
}
int main(void) {
int n, m;
int q, i;
FILE *f = fopen("strmatch.in", "r");
fgets(A, MAX_LEN + 1, f);
n = strlen(A) - 1;
fgets(A + n + 1, MAX_LEN + 1, f);
m = strlen(A + n) - 1;
fclose(f);
process(A, n + m + 1);
i = 0;
q = 0;
while (i < m && q < MAX_POS) {
if (Z[i + n] == n) {
pos[q++] = i - 1;
}
i++;
}
while (i < m) {
q += (Z[i + n] == n);
i++;
}
f = fopen("strmatch.out", "w");
fprintf(f, "%d\n", q);
q = MIN(q, MAX_POS);
for (int i = 0; i < q; i++) {
fprintf(f, "%d ", pos[i]);
}
fclose(f);
return 0;
}