云大数据结构课程教学课件第4章串47.ppt

* 数据结构 * 设S=“ababcabcacbab” T=“abcac” a b a b c a b c a c b a b a b c a c i=2 j=0 i=3 j=1 i=4 j=2 i=5 j=3 i=6 j=4 i指针回溯的位置为：i=i-j+1（i的值为3） * 数据结构 * a b a b c a b c a c b a b 设S=“ababcabcacbab” T=“abcac” a b c a c i=3 j=0 i指针回溯的位置为：i=i-j+1（i的值为4） * 数据结构 * a b a b c a b c a c b a b 设S=“ababcabcacbab” T=“abcac” a b c a c i=4 j=0 i指针回溯的位置为：i=i-j+1（i的值为5） * 数据结构 * a b a b c a b c a c b a b 设S=“ababcabcacbab” T=“abcac” a b c a c i=5 j=0 i=6 j=1 i=7 j=2 i=8 j=3 i=9 j=4 i=10 j=5 返回子串的位置为：i-j+1=6（串的起始位置从1开始算起） * 数据结构 * int index(s,t) seqstring *s,*t; { int i=0,j=0; while ((is?curlen)(jt ?curlen)) if (s ?ch[i]==t ?ch[j] {i++;j++;} else {i=i-j+1;j=0; if (i(s ?curlen - t ?curlen)) return(-1); } if (j==t ?curlen) return (i-j+1) else return (-1); } 朴素的模式匹配算法描述如下： * 数据结构 * int index(s,t) seqstring *s,*t; { int i=0,j=0; while ((is?curlen)(jt ?curlen)) if (s ?ch[i]==t ?ch[j] {i++;j++;} else {i=i-j+1;j=0; if (i(s ?curlen - t ?curlen)) return(-1); } if (j==t ?curlen) return (i-j+1) else return (-1); } 算法分析： 最好情况下平均时间复杂度为：O(n+m) 最坏情况下平均时间复杂度为：O(nm) 朴素的模式匹配算法描述如下： * 数据结构 * a b a b c a b c a c b a b a b c a c i=2 j=0 i=3 j=1 i=4 j=2 i=5 j=3 i=6 j=4 当此次匹配不成功时，根据匹配的部分结果，模式应向右移动3位，从第二个字开始比较。 a b a b c a b c a c b a b a b c a c i=6 j=1 i=7 j=2 i=8 j=3 i=9 j=4 i=10 j=5 提出一个问题：当匹配不成功时，模式应该向右移动多少位，从第几个字符开始比较？ 朴素的匹配算法存在的问题：每次匹配不成功，模式仅向右移动一位， 效率太低。当匹配不成功时，能否利用前次匹配的部分结果将模式尽 可能地向右移动，再进行比较，从而提高算法的效率。 * 数据结构 * KMP匹配算法 KMP 算法是在朴素匹配算法基础上进行改进而得到的，由三位研究算法的人同时发现，他们是：D.E.Knuth, J.H.Morris和V