模式匹配中的一些小技巧以及一些杂乱的东西

模式匹配中的一些小技巧以及一些杂乱的东西

关于模式匹配问题,有一些比较杂的内容我不太清楚应该归类到哪里,其中有一部分一般可能无法派上用场,但是有一些也十分重要,因此全放到了这里。

  1. 如果模式序列中所有元素都不相同,那么在使用暴力模式匹配方法 (Brute Force Pattern Search) 时可以做一点微小的优化,如果我们在i处发现长序列与模式序列的第一个元素一样,这时我们会开始逐个元素匹配,如果在模式序列的第j处发现一个不匹配的字符,那么我们可以直接从i + j + 1处开始继续从模式序列的第一个元素开始尝试匹配,而不用再从i  + 1处开始,这得益于模式序列中所有元素都不相同。【从感觉的角度上想,这其实也略微有一些KMP (KMP (Knuth Morris Pratt) Pattern Searching) 的思想】
  2. 如果长序列长度n等于模式序列长度m,那么我们可以不使用任何复杂的模式匹配算法,直接遍历尝试匹配,复杂度O(n)。
  3. 显然,如果长序列的长度n小于模式序列的长度m,必然无法完成匹配,如果在输入数据不保证n大于等于m的时候,我们应当进行额外的检查。

Brute Force Pattern Search

Brute Force Pattern Search

模式匹配 (Pattern Searching)

暴力模式匹配,也可以叫做简单模式匹配。它的逻辑十分简单,代码容易实现。给出一个长序列和一个模式序列(常是字符串,或者一串数),要在长序列中找到模式序列的出现位置、出现次数等。最直接能想到的方法就是这种,对于长度为n的长序列、长度为m的模式序列,只要写两层循环,暴力尝试m*n种匹配方式,即O(mn)复杂度,就可以找到。缺点是十分耗时。

#include <iostream>
#include <string>

using namespace std;
void search(const string &pat, const string &txt) {
    int pat_len = pat.size();
    int txt_len = txt.size();
    for (ULL i = 0; i <= txt_len - pat_len; i++) {
        if (pat[0] == txt[i]) {
            int j;
            for (j = 1; j < pat_len; j++) {
                if (pat[j] != txt[i + j]) break;
            }
            if (j == pat_len) {
                /*
                 *  found the pattern string
                 *  do something here
                 */
            }
        }
    }
}

int main(void) {

    return 0;
}

相关阅读:

KMP (Knuth Morris Pratt) Pattern Searching:

KMP是一种常用的高效的匹配算法,它减少了暴力匹配方法中一些不必要的匹配,特别是对于模式序列中有着明显重复的模式(如:aaaaaaab),能够提升匹配效率。

Rabin-Karp Algorithm

Rabin-Karp Algorithm利用提前比较hash值来减少暴力匹配的次数,它优越的关键在于给出了由一个序列hash值求得下一个序列hash值的O(1)时间复杂度方法。