此算法的思想是直截了当的，正如算法4.1中所描述的那样，将主串S中某个位置i起始的子串和模式串T相比较。即从 j=0 起比较 S[i+j] 与 T[j]，若相等，则在主串 S 中存在以 i 为起始位置匹配成功的可能性，继续往后探索( j逐步增1 )，直至T串中最后一个字符比较相等为止，否则改从主串的下一个字符起重新开始进行下一轮的"匹配"，即将串T向后滑动一位，即 i 增1，而 j 退回至0，重新开始新一轮的匹配。
模式匹配的基本思想已经在算法4.1中描述清楚了，只是在算法4.1中利用了求子串和串比较等基本操作，在此则直接进行两个串中对应字符的比较。
算法 4.6int Index_BF ( char S [ ], char T [ ], int pos )
{
// 若串 S 中从第pos(1≤pos≤StrLength(S))个字符起存在和
// 串 T 相同的子串，则称匹配成功，返回第一个这样的子串
// 在串 S 中的位置，否则返回 0
i = pos-1; j = 0;
while ( S[i+j] != '\0'&& T[j] != '\0')
if ( S[i+j] == T[j] ) j ++; // 继续比较后一字符
else { i ++; j = 0; } // 重新开始新的一轮匹配
if ( T[j] == '\0') return (i+1); // 匹配成功
注意匹配成功时，函数返回的值是"子串在主串中的位置"，即子串中第1个字符在主串字符序列中的 "位置"，而非该字符在存储结构数组中的下标。
因为在最坏情况下，对i的每个值，j++需执行n-1次。
} // Index_BF
容易看出，此算法的时间复杂度为O(m
n)，其中
m 和 n 分别为S串和T串的长度。一般情况下，算法4.6的实际执行效率与字符 T[0] 在串S中是否频繁出现密切相关。对于一般文稿中串的匹配，算法4.6的时间复杂度可降为O (m+n)，因此在多数的实际应用场合下被应用。
|
|||
|
你能否举出一个使算法4.6运行处最坏情况的例子？
例如，S是一般的英文文稿，T ="a cat"，S中有5% 的字母是 'a'，则在算法4.6执行过程中，对于95% 的情况可以只进行一次对应位的比较就将T向右滑动一位，时间复杂度下降为O (m)。