KMP算法 在本文中将使用始于零的数组来表示字符串比如若字符串S  ABC则S表示字符C这种表示方法与C语言一致 在计算机科学中克努斯莫里斯普拉特字符串查找算法英語KnuthMorrisPratt algorithm简称为KMP算法可在一个字符串S内查找一个词W的出现位置一个词在不匹配时本身就包含足够的信息来确定下一个匹配可能的开始位置此算法利用这一特性以避免重新检查先前配對的字符 这个算法由高德纳和沃恩普拉特在年构思同年詹姆斯H莫里斯也独立地设计出该算法最终三人于年联合发表