第7讲特殊的线性表——串资料.ppt

例：主串S=ababcabcacbab，模式T=abcac a b a b c a b c a c b a b a b c a c i=7，j=5失败 i回溯到4，j回溯到1 第 3 趟 i j 模式匹配——BF算法 例：主串S=ababcabcacbab，模式T=abcac a b a b c a b c a c b a b a b c a c i=4，j=1失败 i回溯到5，j回溯到1 第 4 趟 i j 模式匹配——BF算法 例：主串S=ababcabcacbab，模式T=abcac a b a b c a b c a c b a b a b c a c i=4，j=1失败 i回溯到5，j回溯到1 第 4 趟 i j 模式匹配——BF算法 例：主串S=ababcabcacbab，模式T=abcac a b a b c a b c a c b a b a b c a c i=5，j=1失败 i回溯到6，j回溯到1 第 5 趟 i j 模式匹配——BF算法 例：主串S=ababcabcacbab，模式T=abcac a b a b c a b c a c b a b a b c a c i=5，j=1失败 i回溯到6，j回溯到1 第 5 趟 i j 模式匹配——BF算法 例：主串S=ababcabcacbab，模式T=abcac a b a b c a b c a c b a b a b c a c i=11，j=6，T中全部字符都比较完毕，匹配成功。 第 6 趟 i j i j i j i j i j 模式匹配——BF算法 int BF(SString S[], SString T[]) { i=1; j=1; while (i=S[0]j=T[0]) { if (S[i]==T[j]) { i++; j++; } else { i=i-j+2; j=1; } } if (jT[0]) return (i-j+1); else return 0; } 模式匹配——BF算法 int BF(SString S[], SString T[]) { i=1; j=1;start=1; while (i=S[0]j=T[0]) { if (S[i]==T[j]) { i++; j++; } else { start++; i=start; j=1; } } if (jT[0]) return start; else return 0; } 设串S长度为n，串T长度为m，在匹配成功的情况下，考虑两种极端情况： ⑴ 最好：不成功的匹配都发生在串T的第一个字符。 例如：S=aaaaaaaaaabcdccccc T=“dcd 模式匹配——BF算法 设串S长度为n，串T长度为m，在匹配成功的情况下，考虑两种极端情况： 设匹配成功发生在si处，则在i-1趟不成功的匹配中共比较了i-1次，第i趟成功的匹配共比较了m次，所以总共比较了i-1+m次，所有匹配成功的可能情况共有n-m+1种，则： ⑴ 最好：不成功的匹配都发生在串T的第一个字符。 模式匹配——BF算法 设串S长度为n，串T长度为m，在匹配成功的情况下，考虑两种极端情况： 例如：S=aaaaaaaaaaabccccc T=aaab ⑴ 最坏：不成功的匹配都发生在串T的最后一个字符。 模式匹配——BF算法 设串S长度为n，串T长度为m，在匹配成功的情况下，考虑两种极端情况： 设匹配成功发生在si处，则在i-1趟不成功的匹配中共比较了(i-1)×m次，第i趟成功的匹配共比较了m次，所以总共比较了i×m次，因此 ⑴ 最坏：不成功的匹配都发生在串T的最后一个字符。 模式匹配——BF算法 疑问