KMP算法的时间复杂度为什么是O(n)

主串T，比较串P，
由于KMP算法的思想是主串不回溯的简化算法，执行的时候呢在串比较的扫描里面要么执行POST和POSP，要么执行NEXT[]数组的右移，然后比较，所以字符比较最多就是为O（LenthT）,即不会超过O（n）
其实KMP看起来很吓人，但是你抓住它的思想“主串不回溯”就很简单了.
给你网上的详细解释:http://sundful.javaeye.com/blog/263847

主串T，比较串P，
由于KMP算法的思想是主串不回溯的简化算法，执行的时候呢在串比较的扫描里面要么执行POST和POSP，要么执行NEXT[]数组的右移，然后比较，所以字符比较最多就是为O（LenthT）,即不会超过O（n）
其实KMP看起来很吓人，但是你抓住它的思想“主串不回溯”就很简单了.

KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称KMP算法）。KMP算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next()函数，函数本身包含了模式串的局部匹配信息。