Pagini recente » Cod sursa (job #2326440) | Cod sursa (job #1280914) | Cod sursa (job #1504289) | Cod sursa (job #695215) | Cod sursa (job #638664)
Cod sursa(job #638664)
#include <stdio.h>
#include <string.h>
#define maxlen 2000002
//#define MIN(A, B) ((A) < (B)) ? (A) : (B)
char A[maxlen], B[maxlen], m, n;
int pi[maxlen];
void prefix() {
int k = 0;
pi[1] = 0;
int i;
for (i = 2; i <= m; i++) {
while (k && A[k + 1] != A[i])
k = pi[k];
if (A[k + 1] == A[i])
k = k + 1;
pi[i] = k;
}
for (i = 0; i <= m; i++)
printf("%d ", pi[i]);
}
int main() {
FILE *in = fopen("strmatch.in", "r");
fgets(A, maxlen, in);
fgets(B, maxlen, in);
fclose(in);
m = strlen(A);
n = strlen(B);
m--;
n--;
int i;
for (i = m; i > 0; i--)
A[i] = A[i - 1];
A[0] = ' ';
for (i = n; i > 0; i--)
B[i] = B[i - 1];
B[0] = ' ';
prefix();
int q = 0, j = 0, ans[1000];
for (i = 0; i < n; i++) {
while (q && A[q + 1] != B[i])
q = pi[q];
if (A[q + 1] == B[i])
q++;
if (q == m) {
q = pi[m];
j++;
if (j < 1000)
ans[j - 1] = i - m;
}
}
FILE *out = fopen("strmatch.out", "w");
fprintf(out, "%d\n", j);
int min = (j < 1000) ? j : 1000;
for (i = 0; i < min; i++)
fprintf(out, "%d ", ans[i]);
fclose(out);
return 0;
}