为了便于说明问题，先将算法4.6改写为下列形式，并观看一个实例的匹配过程。
算法 4.7int Index_BF1 ( char S [ ], char T [ ], int pos )
{
// 若串 S 中从第pos(1≤pos≤StrLength(S))个字符起存在
// 和串 T 相同的子串，则称匹配成功，返回第一个这样的子串
// 在串 S 中的位置，否则返回 0
i = pos-1; j = 0;
while ( S[i] != '\0'&& T[j] != '\0')
if ( S[i] == T[j] )
{ i++; j ++; } // 继续比较后一字符
else { i = i-j+1; j = 0; } // 重新开始新的一轮匹配
if ( T[j] == '\0') return (i-j); // 匹配成功
else return 0; // 串S中(第pos个字符起)不存在和串T相同的子串
} // Index_BF1
例如按此算法进行模式串 T = "abcac" 和主串 S ="ababcabcabcacabca" 在 pos=0 的情况下匹配的过程如演示所示。
| |||
|
不知道你看了这个匹配过程之后有什么想法？是什么原因造成最坏情况下出现的O(m
n)时间复杂度？
| |||
|