首页 > 代码库 > [Algorithm] Pattern Matching
[Algorithm] Pattern Matching
1.1 蛮力算法
1.1.1 算法描述
蛮力串匹配是最直接最直觉的方法。可假想地将文本串和模式串分别写在两条印有等间隔方格的纸带上,文本串对应的纸带固定,模式串纸带的首字符与文本串纸带的首字符对齐,两个都沿水平方向放置。于是,只需将P(长度m)与T(长度n)中长度为m的n - m + 1个子串逐一对比,即可确定可能的匹配位置。
不妨按自左向右的次序考查各子串。在初始状态下,T的前m个字符将与p的m个字符两两对齐。接下来,自左向右检查相互对齐的这m对字符:若当前字符对相互匹配,则转向下一对字符;反之一旦失配,则说明在此位置文本串与模式串不可能完全匹配,于是可将P对应的纸带右移一个字符,然后从其首字符开始与T中对应的新子串重新对比。若经过检查,当前的m对字符均匹配,则意味着整体匹配成功,从而返回匹配子串的位置。
蛮力算法的正确性显而易见:既然只有在某一轮的m次比对全部成功之后才成功返回,故不至于误报;反过来,所有对齐位置都会逐一尝试,故亦不至漏报。
1.1.2 算法实现
给出蛮力算法的两个实现版本。两者原理相同、过程相仿,但分别便于引入后续的不同改进算法,故在此先做一比较。
// #1 int match(char* P, char* T) { size_t n = strlen(T), i = 0; size_t m = strlen(P), j = 0; while (j < m && i < n) { if (T[i] == P[j]) { i++; j++; } else { i -= j; j = 0; } } return i - j; }
如上版本1借助整数i和j,分别指示T和P中当前接受比对的字符T[i]和P[j]。若当前字符对匹配,则i和j同时递增以指向下一个字符。一旦j增长到m则意味着发现了匹配,即可返回P相对于T的对齐位置i - j。一旦当前字符对失配,则i回退并指向T中当前对齐位置的下一字符,同时j复位P的首字符处,然后开始下一轮比对。
// #2 int match(char* P, char* T) { size_t n = strlen(T), i = 0; size_t m = strlen(P), j; for (i = 0; i < n - m + 1; i++) { for (j = 0; j < m; j++) if (T[i + j] != P[j]) break; if (j >= m) break; } return i; }
如上版本2借助整数i指示P相对于T的对齐位置,且随着i不断递增,对齐的位置逐步右移。在每一对齐位置i处,另一整数j从0递增至m - 1,依次指示当前接收比对的字符为T[i + j]与P[j]。因此,一旦发现匹配,即可直接返回当前的对齐位置i。
1.1.3 时间复杂度
从理论上讲,蛮力算法之多迭代n - m + 1轮,且各轮至多需进行m次比对,故总共只需做不超过(n - m + 1) * m次比对。因为m << n,渐进的时间复杂度为O(n * m)。
[Algorithm] Pattern Matching