gpt4 book ai didi

string - knuth morris pratt 算法中字符串中的特定字符最多与字符串进行比较的次数?

转载 作者:塔克拉玛干 更新时间:2023-11-03 05:21:36 25 4
gpt4 key购买 nike

T:String
P:pattern

在 knuth morris pratt 算法中,字符串 (T) 中的特定字符与模式 (P) 进行比较的最大次数是多少?

最佳答案

|P|。这是一个例子:

P = aaa...a(n 次)T = aaa...a(n 次)b

当我们到达b时,计数器的当前值为n。每次比较都恰好减少一个。因此,它恰好进行 n 次迭代,直到达到零。

为什么是上限?

显然比较的次数最多为|P|(每次比较至少使前缀函数的值减1,永远不能超过|P|).

关于string - knuth morris pratt 算法中字符串中的特定字符最多与字符串进行比较的次数?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/29735615/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com