字符串模式匹配（BF--RK--BM--KMP）

作者:神秘网友发布时间:2020-09-30 09:45:11

字符串模式匹配（BF--RK--BM--KMP）

bool patternMatching(string pattern, string value) {
        int m = pattern.size();
        int n = value.size();
       
        for(int i = 0; i <= (n-m); i++){
            int begin = i;
            bool flag = true;
            for(int j = 0; j < m; j++){
                if(pattern[j]!= value[begin+j]){
                    flag = false;
                    break;
                }    
            }
            if(flag) return true;
        }
        return false;
    }

上文的BF算法，最坏的情况可能可能是这样

pattern：aaab
value： aaaaaaaaaaaaaaaaab

每一轮里面的for循环都会跑完，也就是最大的时间复杂度。
所以可以考虑通过计算哈希的方法，比如计算模式串的哈希值，然后在主串中计算相同长度的哈希，如果相等表示匹配成功。
注意哈希冲突。

RK算法全程Rabin-Karp，该算法的2位发明者Rabin和Karp的名字组合而成。该算法的核心思想就是通过比较2个字符串的hashcode来判断是否包含对方。

计算哈希的方法有很多，
（1）比如因为字母有26位，可以转化为26进制数。
bedc = 2 *(26^3) + 5 * (26^2) + 4 * 26 + 3

这样哈希冲突大大减小，但可能超出整型范围，需要进行取模。
（2）可以使用按位相加，但是可能出现哈希冲突。
注意：如果在主串中更新哈希值的过程中不做任何处理，相当于还是进行了O（mn）次，没有任何改进，所以每次更新哈希值可以将前一个字符剔除，后一个字符加入。

// 虽然使用了哈希，复杂度还是O（mn）
bool patternMatching(string pattern, string value) {
        int m = pattern.size();
        int n = value.size();
        int patternCode = hash(pattern);
        int strCode = hash(value.substr(0, m));
        for(int i = 0; i <= (n-m); i++){
            strCode = hash(value.substr(i,m));
            if(strCode == patternCode && compareString(i, value, pattern)){
                return true;
            }
        }
        return false;
    }
    int hash(string str){
        int hashcode = 0;
        for(char c: str){
            hashcode += (c - 'a');
        }
        return hashcode;
    }
    bool compareString(int i , string s, string p){
        string temp = s.substr(i, i+p.size());
        return temp == p;
    }

bool patternMatching(string pattern, string value) {
        int m = pattern.size();
        int n = value.size();
        int patternCode = hash(pattern);
        int strCode = hash(value.substr(0, m));
        for(int i = 0; i <= n-m; i++){
            if(strCode == patternCode && compareString(i, value, pattern)){
                return true;
            } 
           if(i!= n-m) { //i+m <n, 计算下一轮的哈希
                strCode = nextHash(value,strCode, i, i+m);
            }
        }
        return false;
    }

    int hash(string str){
        int hashcode = 0;
        for(char c: str){
            hashcode += (c - 'a');
        }
        return hashcode;
    }
    int nextHash(string s, int hash, int before, int next){
        hash -= (s[before] -'a');
        hash += (s[next] - 'a');
        return hash;
    }
    bool compareString(int i , string s, string p){
        string temp = s.substr(i, i+p.size());
        return temp == p;
    }

字符串比较是从后往前。

坏字符规则

坏字符就是模式串和主串比较时，最后一个不匹配的字符。
当监测到坏字符，不需要一位位移动，如果坏字符和模式串中某一个字符匹配，直接移动将他们匹配；
字符串模式匹配（BF--RK--BM--KMP）

如果不相等直接移动：
字符串模式匹配（BF--RK--BM--KMP）
看一个例子：

注意??：查找模式串中是否存在坏字符，也是从右向左，找到第一个和坏字符匹配的字符串进行匹配。

 bool patternMatching(string pattern, string value) {
        int m = pattern.size();
        int n = value.size();
        int start = 0;
        while(start <= n-m){
            int i;
            for(i = m-1; i>=0; i--){
                if(pattern[i]!= value[start+i]){
                    break;
                }
            }
            if(i < 0) return true; // sucess;
            int charIndex = findCharacter(pattern, value[start+i], i);
            int off = charIndex == -1 ? i+1:i-charIndex;
            start += off;
        }
        return false;
    }
    int findCharacter(string pattern, char badCharacter, int index){
        for(int i = index-1; i>=0; i--){
            if(pattern[i] == badCharacter) return i;
        }
        return -1;
    }

好后缀规则

好后缀规则就是模式串中和字串中匹配的后缀
字符串模式匹配（BF--RK--BM--KMP）
如果模式串中有相同的后缀，我们可以挪动模式串，让这个片段和好后缀对齐：

如果模式串中不存在和好后缀相同的片段，是否可以直接将模式串挪到好后缀之后？？

不可以直接挪动整个的模式串，还需要判断模式串的前缀时候和好后缀的后缀匹配
字符串模式匹配（BF--RK--BM--KMP）

什么时候使用坏字符，什么时候使用好后缀呢？
每一轮进行计算，哪一种规则可以挪动的距离更多就使用哪一种。

kmp算法由三位科学家D.E.Knuth, J.H.Morris and V.R.Pratt提出，KMP这个算法名字就是取自三个人的姓氏首字母。
整体思路：
和BM类似，如果遇到坏字符，应该如何移动呢？直接移动整个模式串？当然不可以。应该利用已经匹配的字符串，是否主串的后缀和模式串的前缀相同，如果相同，重合移动，如果不同，直接移动整个串，看一个例子：
发现坏字符A
字符串模式匹配（BF--RK--BM--KMP）
注意：最长可匹配后缀字串，最长可匹配前缀子串

挪动重合两个子串，发现新的坏字符

计算现在的最长可匹配前缀字串和后缀子串

挪动，进行下一轮比较：

以上就是KMP算法的整体思路：在已匹配的前缀当中寻找到最长可匹配后缀子串和最长可匹配前缀子串，在下一轮直接把两者对齐，从而实现模式串的快速移动。

那么如何计算最长可匹配后缀子串，最长可匹配前缀子串？

我们可以提前缓存到一个数组中，这个集合就是next，生成他就是最大的难点。

数组的下标表示已经匹配的前缀的下一个位置， 元素的值表示“最长可匹配前缀字串的下一个位置”

字符串模式匹配（BF--RK--BM--KMP）
next 数组的使用

next 数组的生成：
设置变量i,j。 i 表示以匹配前缀的下一个位置，也就是数组下标。
j表示最长可匹配前缀字串的下一个位置，也就是带填充的数组元素值。

i = 0, j = 0
next [i] = 0; i++

字符串模式匹配（BF--RK--BM--KMP）

next[1] = 0, i++

字符串模式匹配（BF--RK--BM--KMP）
判断如果pattern[j] != pattern[i-1], 即G！=T，最长可匹配前缀字串不存在

next[2] = 0; i++

字符串模式匹配（BF--RK--BM--KMP）

判断pattern[j] == pattern[i-1]
next[3] = next[2]+1; j++; i++

字符串模式匹配（BF--RK--BM--KMP）

判断pattern[j] == pattern[i-1] ,
next[4] = next[3]+1, j++; i++

字符串模式匹配（BF--RK--BM--KMP）

判断pattern[j] == pattern[i-1] ,
next[5] = next[4]+1, j++; i++

继续i++,
pattern[j] ！= pattern[i-1] ,这时候怎么办呢？

字符串模式匹配（BF--RK--BM--KMP）
计算“GTGTGC” 最长可匹配前缀字串问题，转化为计算GTGC的最长可匹配的问题。

这样的问题转化，也就相当于把变量j回溯到了next[j]，也就是j=1的局面（i值不变）

回溯之后pattern[j] != pattern[i-1] ，继续转化
字符串模式匹配（BF--RK--BM--KMP）

依然是pattern[j] != pattern[i-1], j 不能回溯了，所以next[6] = 0;

伪代码

 对模式串进行预处理，求出next 数组
 进入主循环，遍历主串
 		
 		比较主串和模式串的字符
 		如果发现坏字符，查询next 数组，得到匹配前缀所对应的最长可匹配前缀字串，移动模式串到对应的位置
		如果当前字符匹配，那么继续循环

class Solution {
public:
    bool patternMatching(string pattern, string value) {
        int m = pattern.size();
        int n = value.size();
        next.resize(m+1);
        next[0] = 0; 
        next[1] = 0;
        getNext(pattern);
        int j = 0;
        for(int i = 0; i < value.size(); i++){
            while(j > 0 && value[i]!= pattern[j]) j = next[j];
            if(value[i] == pattern[j])j++;
            if(j == m) return true;
        }
        return false;
    }
    void getNext(string pattern){
        int j = 0, i = 2;
        for(; i < pattern.size(); i++){
            while(j!=0 && pattern[j]!=pattern[i-1]) j = next[j];
            if(pattern[j] == pattern[i-1])j++;
            next[i] = j;
        }

    }
private:
    vector<int> next;
};

空间复杂度O（m）, 时间复杂度O（m+n）