KMP的失效函数

发布于 2024-11-18 16:38:43 字数 132 浏览 1 评论 0原文

最近学习了KMP字符串匹配算法，几乎全部掌握了。但我不明白的是如何在 O( length_of_pattern ) 中构建失败函数。我不需要代码，如果可能的话，我需要清晰的解释。提前致谢！

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

痴情换悲伤 2024-11-25 16:38:43

来自此站点：

KMP 算法预处理模式P 通过使用先前执行的比较来计算指示最大可能偏移 s 的故障函数 f。

具体地，失效函数f(j)被定义为作为P[i的后缀的P的最长前缀的长度。。 j]。

这是一个构造的伪代码，我想你可以在网站上得到详细的解释

        KNUTH-MORRIS-PRATT FAILURE (P)

            Input:    Pattern with m characters
            Output: Failure function f for P[i . . j]

            i ← 1
            j ← 0
            f(0) ← 0
            while i < m do    /// your complexity will be O(length of pattern)
                if P[j] = P[i]
                    f(i) ← j +1
                     i ← i +1
                      j← j + 1
                else if (j != 0)
                     j ← f(j - 1)
                else
                    f(i) ← 0
                    i ← i +1

希望它能回答你的问题

from this site:

The KMP algorithm preprocess the pattern P by computing a failure function f that indicates the largest possible shift s using previously performed comparisons.

Specifically, the failure function f(j) is defined as the length of the longest prefix of P that is a suffix of P[i . . j].

Here is a pseudo code for the construction, I guess you can get the detail of the explaination on the site

        KNUTH-MORRIS-PRATT FAILURE (P)

            Input:    Pattern with m characters
            Output: Failure function f for P[i . . j]

            i ← 1
            j ← 0
            f(0) ← 0
            while i < m do    /// your complexity will be O(length of pattern)
                if P[j] = P[i]
                    f(i) ← j +1
                     i ← i +1
                      j← j + 1
                else if (j != 0)
                     j ← f(j - 1)
                else
                    f(i) ← 0
                    i ← i +1

Hope it answers your question

回复收藏 0 原文

~没有更多了~