Knuth Morris Pratt算法的实现

Question

我正在尝试实现KMP算法。"if (Wi == Sm + i)“部分返回索引超出范围的异常，我无法让它工作。

我在维基百科上看了下面的例子：https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm

static int[] KMPTable(string W)
    {
        int[] T = new int[W.Length];
        int pos = 2;
        int cnd = 0;

        T[0] = -1;
        T[1] = 0;

        while (pos < W.Length)
        {
            if (W[pos - 1] == W[cnd])
            {
                T[pos] = cnd + 1;
                cnd = cnd + 1;
                pos = pos + 1;
            }
            else
                if (cnd > 0)
                {
                    cnd = T[cnd];
                }
                else
                {
                    T[pos] = 0;
                    pos = pos + 1;
                }
        }

        return T;
    }

    static int[] KMPSearch(string S, string W)
    {
        int m = 0;
        int i = 0;
        int[] kmpNext = KMPTable(S);
        List<int> result = new List<int>();

        while (m + i < S.Length)
        {
            if (W[i] == S[m + i])
            {
                if (i == W.Length - 1)
                {
                    result.Add(m);
                }
                    i = i + 1;
            }
            else
            {
                m = m + i - kmpNext[i];
                if (kmpNext[i] > -1)
                    i = kmpNext[i];
                else
                    i = 0;
            }
        }
        return result.ToArray();
    }

Answer 1

当m+i< S.Length时，可能是Wi超出了它的索引。尝试使用分步调试进行检查。