problem : NAJPF - Pattern Find
It seemed like a straight-forward implementation of KMP algorithm but it’s showing wrong answer, would someone point out the error in the following code, please? Thanks in advance.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 1000002
int ara [N], k;
int* failure_function (char* P)
{
int i = 1, j = 0, length = strlen (P);
static int F[N];
F[0] = 0;
while (i < length) {
if (P[i] == P[j]) {
F[i] = j + 1;
i += 1;
j += 1;
}
else if (j > 0)
j = F[j - 1];
else {
F[i] = 0;
i += 1;
}
}
return F;
}
int KMP (char* T, char* P)
{
int i = 0, j = 0, count = 0, length = strlen (T);
int *F = failure_function (P);
memset (ara, 0, sizeof (ara));
k = 0;
while (i < length) {
if (T[i] == P[j]) {
i += 1;
j += 1;
if (j == strlen (P)) {
//printf("match found at index %d\n", i - j);
//printf("i = %d j = %d\n", i, j);
ara [k ++] = i - j + 1;
j = F [j - 1];
count ++;
}
}
else if (j > 0)
j = F[j - 1];
else
i += 1;
//printf("%c %c\n", T [i], P [j]);
}
return count;
}
int main ()
{
freopen ("a.txt", "r", stdin);
int t;
char T [N], P [N];
scanf ("%d ", &t);
while (t --) {
scanf ("%s %s", T, P);
//printf("%s %s\n", T, P);
int ans = KMP (T, P);
if (ans) {
printf("%d\n", ans);
for (int i = 0; i < k; i ++)
printf("%d ", ara [i]);
printf("\n");
}
else
printf("Not found\n");
printf("\n");
}
return 0;
}