数据结构与算法
-
编辑 删除
KMP字符串匹配算法
花了一天，边玩边看KMP字符串匹配算法，效率真tm低，不够还算搞明白了，看在周末的份上，原谅自己了，呵呵。记录一下。命题：设计算法，在字符串s中，从pos位置开始，查找第一个与目标字符串t相同的子字符串的起始位置。kmp算法实现：第一步，预处理目标字符串t，求出t中每一个字符在与源字符串s中字符不等时移到的位置。方法是根据如下公式next[0] = -1;next[j] = max{k| 0<k<j && "t0t1...t(k-1)" == "t(j-k)t(j-k+1)...t(j-1)"};next[j] = 0; 此公式可如下证明首先，假设目标字符串下一次移动到k位置
