dave - 1 month ago 5x
C# Question

# Displaying result of KMP compute prefix function

I'm trying to solve homework for school, it concerns KMP algorithm. Here is my compute prefix function, it is suppose to output a prefix table, however all it does is every time it returns all 0s. Could help me understand what am I doing wrong? Thanks!

``````static int[] computePrefixFunction(string P)
{
int m = P.Length;
int[] pi = new int[m];
pi[1] = 0;
int k = 0;

for (int j = 2; j < m; j++)
{
while (k > 0 && P[k + 1] != P[j])
{
k = pi[k];
}
if (P[k+1] == P[j])
{ k = k + 1; };
pi[j] = k;
}

for (int i = 0; i < pi.Length; i++)
{
Console.WriteLine(pi[i]);
}
return pi;
}
``````

You a have messed up indexes offsets. Here is fixed version:

``````static int[] computePrefixFunction(string P)
{
int m = P.Length;
int[] pi = new int[m];
int k = 0;

for (int j = 1; j < m; j++)
{
k = pi[j - 1];

while (k > 0 && P[k] != P[j])
k = pi[k-1];

if (P[k] == P[j])
k = k + 1;

pi[j] = k;
}

return pi;
}
``````

Live demo: https://dotnetfiddle.net/YQknMp