Pagini recente » Cod sursa (job #1765956) | Cod sursa (job #959771) | Borderou de evaluare (job #324414) | Cod sursa (job #72714) | Cod sursa (job #1306976)
#include <stdio.h>
#include <string.h>
#define NMAX 2000000
#define BMAX 1000
char A[NMAX + 2], B[NMAX + 2];
int pi[NMAX + 2], buff[BMAX + 1], sp;
int M, N;
void preproc()
{
int k = 0, q;
for (q = 1; q < M; q++) {
while ((k > 0) && (A[k] != A[q])) {
k = pi[k - 1];
}
if (A[k] == A[q]) {
k++;
}
pi[q] = k;
}
}
void KMP()
{
int q = 0, i;
for (i = 0; i < N; i++) {
while ((q > 0) && (A[q] != B[i])) {
q = pi[q - 1];
}
if (A[q] == B[i]) {
q++;
}
if (q == M) {
sp++;
if (sp <= BMAX) {
buff[sp] = i - M + 1;
}
}
}
}
int main()
{
FILE *fin, *fout;
fin = fopen("strmatch.in", "r");
fout = fopen("strmatch.out", "w");
fgets(A, sizeof(A), fin);
fgets(B, sizeof(B), fin);
M = strlen(A) - 1;
N = strlen(B) - 1;
preproc();
KMP();
fprintf(fout, "%d\n", sp);
int i;
for (i = 1; i <= sp && i <= BMAX; i++) {
fprintf(fout, "%d ", buff[i]);
}
fprintf(fout, "\n");
fclose(fin);
fclose(fout);
return 0;
}