knuth morris pratt算法中字符串中的特定字符与字符串进行比较的最大次数？
knuth morris pratt算法中字符串中的特定字符与字符串进行比较的最大次数？
提问于 2015-04-20 04:43:22
让
T:String
P:pattern在knuth morris pratt算法中，字符串(T)中的特定字符与模式(P)比较的最大次数是多少？
回答 1
Stack Overflow用户
发布于 2015-04-20 05:37:37
|P|。下面是一个示例：
P = aaa...a(n times) T = aaa...a(n times)b
当我们到达b时，计数器的当前值是n。每次比较都恰好减去一次。因此，它精确地进行n迭代，直到它达到零。
为什么它是一个上限？
很明显，比较的次数最多是|P|(每次比较至少减少一个前缀函数的值，并且它永远不能超过|P|)。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/29735615
复制相关文章
相似问题
腾讯云开发者
