dave - 1 year ago 85

C# Question

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 Source

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