我会说,像这样的一个模式xx........x | n times | 并且一个类似于字符串的东西 xxx.........xyx...........xy.... | n-1 times | | n-1 times | 这可能是最糟糕的情况之一,但它仍然是O(m+n)
你可以在这里找到关于KMP算法的任何信息: KMP算法 摘要如下:Knuth、Morris和Pratt通过对朴素算法进行紧密分析,首次发现了线性时间字符串匹配算法。Knuth-Morris-Pratt算法在扫描文本时保留了朴素方法浪费的信息。通过避免这种信息浪费,它实现了O(n + m)的运行时间,在最坏情况下是最优的。也就是说,在最坏情况下,Knuth-Morris-Pratt算法必须至少检查一次文本和模式中的所有字符。你应该能够澄清你对该算法的理解,并在那里找到需要的内容。希望这有所帮助。