首页 > 代码库 > [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