[理学]数据结构 chapter 4 串.ppt

* * 简单模式匹配算法示例 a b a b c a b c a b c a b S pos T i j i j i j 第一趟匹配 i=3,j=3 i=i-j+2=2,回退1 a b a b c a b c a b c a b S T i j 第二趟匹配 i=2,j=1 i=i-j+2=3,前进 a b c a c a b c a c a b a b c a b c a b c a b S T i j 第三趟匹配 i=7,j=5 i=i-j+2=4,回退3 a b c a c i j i j i j i j * * 简单模式匹配算法的问题 当出现不匹配的时候，主串的指针需要回退，影响效率 极端情况下比较的次数与N×M成正比 经过人们的努力，发现了一种改进算法，它可以在N+M数量级上完成模式匹配。 这种算法称为KMP算法，其改进之处在于：在每一趟比较中，当出现不匹配的情况时，不需要回退主串的指针，而是根据已经得到的“部分匹配”的结果，将子串的指针后移一段距离后再进行比较 * * 改进算法说明示例 a b a b c a b c a b c a b S T i=3 j 第一趟匹配 a b c a c a b a b c a b c a b c a b S T i j=1 第二趟匹配 a b c a c i=7 a b a b c a b c a b c a b S T i 第三趟匹配 a b c a c i=7 j=2 因为主串i=2必然为b,而T(1)=a肯定不匹配 因为主串i=4,5必然为bc,T(1)=a肯定不匹配,主串6为a不需要比较 主串指针无需回退示例 P1≠P2，无法匹配 主串指针没有必要回退 完全取决于模式串 * a b a b c a b c a b c a b a b c a c a b c a c a b c a c i j i j * 主串指针无需回退示例 a b a b c a b c a b c a b a b c a c a b c a c a b c a c i j i j P1≠P2，无法匹配 P1≠P3，无法匹配 P1=P4，无需匹配 主串位置不变 子串调整到合适位置next(j) 相当于模式串自己与自己比较 a b c a c * 如何确定子串调整位置 a b c a b a b c a b c a b c a b c b a i j next(j)=? next(j)=5 next(j)=4 next(j)=3 c a b c b a c a b c b a * 如何确定子串调整位置 a b c a a a b c a b c a b c a a c b a i j next(j)=? next(j)=5 next(j)=4 next(j)=2 c a a c b a next(j)=3 c a a c b a * 如何确定子串调整位置 a a a a a a b c a b c a b a a a c a a i j next(j)=? next(j)=5 a a a c a a a a a c a a next(j)计算 * * c a b c b a c a b c b a next(j) c a a c b a c a a c b a next(j) a a a c a a a a a c a a next(j) j j j * * 讨论一般情况 假设主串为’s1s2…sn’而模式串为’p1p2…pm’，当si≠pj时，模式串应该向右滑行多长的距离？换句话说，主串中第i个字符（i指针不回退）该与模式串中哪个字符比较呢 假设此时应该与模式串中的第k（kj）个字符比较,那么模式中的前k-1个字符必须满足下列关系： 而已经得到的部分匹配结果有： j k * * k值的确定 根据上面的结论有： 对于模式abcac其值为： j 1 2 3 4 5 6 7 8 模式串 a b a a b c a c next(j) 0 1 1 2 2 3 1 2 * * 改进后的算法 当si≠pj时，让主串中的第i个字符与模式中第j=next(j)个字符比较 如果相等则i,j均加1 否则j=next(j)，如果仍然不相等，则这个过程一直进行下去直到 j==0。此时模式 右移一个位置，即从主串的下一个位置(i+1)开始重新进行比较 * * KMP算法C描述 int Index_KMP(SString S, SString T, int pos) { i = pos; j= 1; while(i = S[0] j=T[0]) { if (j==0 || S[i]==T[j]) {i++;j++;} else j=next(j); } if (j T[0])