 # KAN13C - Editorial

Author: Dr. M Sohel Rahman
Tester: Jingbo Shang
Editorialist: Jingbo Shang

Medium

KMP

### PROBLEM:

Given a string S[1…n], for each prefix of S[1…i], calculate largest pre[i], such that S[1…pre[i]] is same as S[i-pre[i]+1,i].

### EXPLANATION:

This is a classical problem in Knuth–Morris–Pratt (KMP) algorithm.
It is easy to see that pre[i]≤pre[i-1]+1, since S[1…pre[i]]=S[i-pre[i]+1…i] and S[1…pre[i-1]]=S[i-pre[i-1]…i-1].
Furthermore, we can “Jump” followed the pre[]. Therefore, we can get the main procedure as following:

``````    pre = 0;  // by the definition of the problem
for (int i = 2; i <= n; ++ i) {
int k = pre[i - 1];
while (k != 0 && s[k + 1] != s[i]) {
k = pre[k];
}
if (s[k + 1] == s[i]) {
pre[i] = k + 1;
} else {
pre[i] = 0; // all failed
}
}
``````

See Wiki Pedia for more details:

``````    http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm
``````

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.
Tester’s solution can be found here.

Can u explain why this code is giving WA
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main()
{
char *str = (char *) malloc(4 * 1000000 * sizeof(char));
int *asv = (int *) malloc(4 * 1000000 * sizeof(int));
long long int i;
long long int j;
long long int k;
long long int l;

``````while (1) {
scanf("%s", str);

if (strcmp(str,"End") == 0)
break;

k = strlen(str);

l = 0;

for (i = 1; i < k; ++i) {
if (str[i] == str)
asv[i] = 1;
else
asv[i] = 0;
}

for (i = 1; i < k; ++i) {
if (asv[i-1] >= 1 && asv[i-1] <= 9) {
j = asv[i-1];
if (str[i] == str[j]) {
asv[i] = j + 1;
}
}
}

for (i = 0; i < k; ++i)
printf("%d ", asv[i]);

printf("\n");

}

free(asv);
free(str);
return 0;
``````

}
It is working fine for all cases in my system.