严蔚敏数据结构kmp算法详解.ppt

4.3.2 KMP 算法 KMP 算法是 D.E.Knuth J.H.Morris 和 V .R.Pratt 共同提出的 , 简称 KMP 算法该算法较 BF 算法有较 大改进 , 主要是消除了主串指针的回溯 , 从而使算法效 率有了某种程度的提高 所谓 真子串 是指模式串 t 存在某个 k(0 k j) 使 得 0 t 1 t k = t j-k t j-k+1 t j 成立 例如 t= aba