Knuth Morris Pratt算法的实现 [英] Knuth Morris Pratt algorithm implementation

问题描述

我正在尝试实现KMP算法.部分如果(W [i] == S [m + i])"返回索引超出范围异常，而我无法使其正常工作.

I'm trying to implement KMP algorithm. Part "if (W[i] == S[m + i])" returns index out of range exception and I can't get it to work.

我在Wikipedia上关注以下示例: https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm

I was following example on Wikipedia: 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();
    }

推荐答案

当m + i< S.Length，则可能是W [i]不在其索引中.尝试通过逐步调试进行检查.

When m + i < S.Length, then it might be W[i] that is out of its index. Try checking with a step-by-step debug.

这篇关于Knuth Morris Pratt算法的实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！