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

Question

让

T:String
P:pattern

knuth morris pratt 算法中字符串（T）中的特定字符与模式（P）进行比较的最大次数是多少？

Answer 1

|P|. 这是一个例子：

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

当我们到达b时，计数器的当前值为n。每次比较都会将其减少一。因此，它会精确地进行n迭代，直到达到零。

为什么它是一个上限？

很明显，比较的次数最多|P|（每次比较都会将前缀函数的值减少至少一个，并且永远不会超过|P|）。