dave dave - 3 months ago 15
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;
}

Answer

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