KMP算法是对一般模式匹配算法的改进，由D.E.Knuth与V.R.Pratt和J.H.Morris同时发现的因此人们称它为克努特-莫里斯-莫拉特操作（简称为KMP算法）。对于一般的模式匹配算法：分别利用两个指针i和j指示主串S和T中的当前正待比较的字符位置。算法的基本思想是：从主串的S的第POS个字符开始起和模式的第一个字符比较之，如相等，则继续逐个比较后续字符；否则从主串的下一个字符起再重新和模式的字符比较之。以此类推，直到模式T中的每个字符依次和主串S中的一个连续字符序列相等，则称匹配成功，则函数值为和模式T中的第一个字符相等的字符在主串S中的序号，否则称匹配不成功，函数值为0.而对于模式匹配的KMP算法可以在O(n+m)的时间数量级上完成串的模式匹