文件名称：蛮力算法-cis_orcad 本地数据库配置方法
文件大小：5.89MB
文件格式：PDF
更新时间：2024-06-28 07:12:12
数据结构 邓俊辉
§11.2 蛮力算法 11.2.1 算法描述 图11.1 串模式匘配癿蛮力算法 蛮力串匹配是最直接最直觉的方法。如 图11.1所示，可假想地将主串和模式串分别 写在两条印有等间距方格的纸带上，主串对 应的纸带固定，模式串纸带的首字符与主串 纸带的首字符对齐，二者都沿水平方向放置。 于是，只需将P与T中长度为m的n-m+1个子串 逐一比对，即可确定可能的匹配位置。 不妨按自左向右的次序考查各子串。在初始状态下，T的前m个字符将与P的m个字符两 两对齐。接下来，自左向右检查相互对齐的这m对字符：若当前字符对相互匹配，则转向下 一对字符；反之一旦失配，则说明在此位置主串与模式串不可能完全匹配，于是可将P对应 的纸带右移一个字符，然后从其首字符开始与T中对应的新子串重新对比。图中，模式串P 的每一黑色方格对应于字符对的一次匹配，每一灰色方格对应于一次失配，白色方格则对应 于未进行的一次比对。若经过检查，当前的m对字符均匹配，则意味着整体匹配成功，从而 返回匹配子串的位置。 蛮力算法的正确性显而易见：既然只有在某一轮的m次比对全部成功之后才成功返回， 故不致于误报；反过来，所有对齐位置都会逐一尝试，故亦不致漏报。 11.2.2 算法实现 以下给出蛮力算法的两个实现版本。二者原理相同、过程相仿，但分别便于引入后续的 不同改进算法，故在此先做一比较。 1 /****************************************************************************************** 2 * Text : 0 1 2 . . . i-j . . . . i . . n-1 3 * ------------------------|-------------------|------------ 4 * Pattern : 0 . . . . j . . 5 * |-------------------| 6 ******************************************************************************************/ 7 int match(char* P, char* T) { //串匘配算法（Brute-force-1） 8 size_t n = strlen(T), i = 0; //主串长度、弼前接叐比对字符癿位置 9 size_t m = strlen(P), j = 0; //模式串长度、弼前接叐比对字符癿位置 10 while (j < m && i < n) //自左向右逐个比对字符 11 if (T[i] == P[j]) //若匘配 12 { i ++; j ++; } //则转刡下一对字符 13 else //否则 14 { i -= j - 1; j = 0; } //主串回退、模式串复位 15 return i - j; //如何通过迒回值，刞断匘配结枅？ 16 } 代码11.1 蛮力串匘配算法（版本一）