我想解决学校的作业,它涉及到KMP算法。这是我的compute prefix函数,它应该输出一个前缀表,然而它所做的只是每次返回全0。你能告诉我我做错了什么吗?谢谢!
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;
}
你把索引偏移量弄乱了。以下是固定版本:
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;
}
实时演示:https://dotnetfiddle.net/YQknMp