17. 字符串匹配算法

17.1 BF算法

Brute Force 缩写，即暴力匹配算法，也称为朴素匹配算法。例如在A字符串中查找B字符串，因此从A字符串的起始位置依次向后匹配，看是否有匹配的字符串。
步骤
首先将原字符串和子串左端对齐，逐一比较；如果第一个字符不能匹配，则子串向后移动一位继续比较；如果第一个字符匹配，则继续比较后续字符，直至全部匹配。
时间复杂度
m：匹配串的长度 n：为主串的长度
每次需要对比 m 个字符，需要对比 n - m + 1 次，所以最坏情况的时间复杂度为 O(n m)。
*应用
效率不高但是实现简单，适用于 主串不是很长的场景。

/**
 * @brief 
 * Brute Force 暴力匹配算法
 * 返回B串在A串中首字母出现的位置，不存在返回-1
 * @param A 
 * @param B 
 * @return int 
 */
int BF(string A,string B){
    int m=A.length(),n=B.length();
    int i=0,j=0;
    while(i<m&&j<n){
        if(A[i]==B[j]){
            i++;j++;
        }else{
            i=i-j+1;//i回退到原位+1的位置
            j=0;
        }
    }
    //遍历完成，如果因为B遍历完,说明匹配，返回起点位置
    if(j==n){
        return i-n+1;
    }
    //如果因为A遍历完，说明不匹配
    return -1;
}

17.2 RK算法

RK算法 全称 Rabin-Karp算法，由发明者 Rabin 和 Karp 名字命名的。
步骤
通过哈希算法对主串中的 n-m+1 个字串分别进行哈希求值，逐个比较hash的大小，如果相等则表示子串与主串匹配了。因为哈希值是数字，数字间比较非常快速，所以查找效率会提高。
时间复杂度
m：匹配串的长度 n：为主串的长度
RK算法时间复杂度 O(m + n)
应用
适用于匹配串类型不多的情况，比如：字母、数字或字母加数字的组合 62 (大小写字母+数字)

//判断A从i开始的字串是否与B相等
bool isMatch(string A,int i,string B,int n){
    for(int j=0;j<n;j++){
        if(A[i+j]!=B[j]){
            return false;
        }
    }
    return true;
}
int RK(string A,string B){
    int m=A.length(),n=B.length();
    int hashA=0,hashB=0;
    //hash初始化
    for(int i=0;i<n;i++){
        hashA+=(A[i]-'a');
        hashB+=(B[i]-'a');
    }
    for(int i=0;i<=m-n;i++){
        //如果hash值相等，看是不是一样，一样就返回
        if(hashA==hashB&&isMatch(A,i,B,n)){
            return i;
        }
        //不一样，计算后一个字串的hash，去掉首字符的hash，加上后一个字符的hash，继续循环
        hashA-=(A[i]-'a');
        hashA+=(A[i+n]-'a');
    }
    return -1;
}

17.3 BM算法

阮一峰-字符串匹配的Boyer-Moore算法和BM算法代码深入剖析
BM算法是高效的字符串匹配算法，比KMP算法效率快3-5倍，全称为Boyer-Moore算法。
使用代码实现该算法有两个关键点：

• 坏字符规则：模式串（短串）从后往前匹配到的第一个不符的字符称为坏字符。这时候只要找到当前坏字符在模式串上一次出现位置，就可：后移位数 = 坏字符的位置 - 搜索词中的上一次出现位置。得到匹配串（长串）的移动位数。
• 好后缀规则：从后往前匹配的相等子串即为好后缀。同样的，后移位数 = 好后缀的位置 - 搜索词中的上一次出现位置。
• 根据坏字符规则和好后缀规则中的较大者作为移动位数。

时间复杂度
m：匹配串的长度 n：为主串的长度
BM算法的时间复杂度是O(N/M)
应用
BM算法比较高效，在实际开发中，特别是一些文本编辑器中，用于实现查找字符串功能。
该算法常用于文本编辑器中的搜索匹配功能，比如GNU grep命令使用的就是该算法。

int getGSMove(vector<int>& suffix,vector<bool>& prefix,int index,int n){
    //好后缀的长度
    int len=n-index-1;
    //如果存在好后缀匹配的前缀
    if(suffix[len]!=-1){
        //后移位数 = 好后缀的位置(index + 1) - 搜索词中的上一次出现位置
        return index+1-suffix[len];
    }
    //如果不存在好后缀匹配的前缀，看子 好后缀是否有前缀匹配
    //j为坏字符，j+1是好后缀的起始位置，j+2是好后缀的第一个子后缀，子后缀的位置不超过m-1
    for(int i=index+2;i<n;i++){
        if(prefix[n-i]){
            return i;
        }
    }
    return 0;
}
/**
 * @brief BM算法
 * 坏字符和好后缀规则
 * 统计模式串每个字符在最后边出现的位置
 * @param A 
 * @param B 
 * @return int 
 */
int BM(string A,string B){
    int m=A.length(),n=B.length();
    if(m<n){
        return -1;
    }
    //建立坏字符数组
    vector<int> bad_table(SIZE,-1);
    for(int i=0;i<n;i++){
        bad_table[B[i]]=i;
    }
    //建立好后缀数组，suffix为后缀字符对应前面的位置，prefix存储是否存在匹配的前缀字串
    vector<int> suffix(n,-1);
    vector<bool> prefix(n,false);
    for(int i=0;i<n-1;i++){
        int j=i;   //从第一个字符开始遍历
        int k=0;   //从最后一个字符
        //从长度为1对比，每次符合条件刷新suffix
        while(j>=0 && B[n-1-k]==B[j]){
            j--;
            k++;
            suffix[k]=j+1;
        }
        if(j==-1){   //说明有前缀字符对应
            prefix[k]=true;
        }
    }
    int i=0;
    while(i<=m-n){
        //找坏字符，从右向左比较
        int j=0;
        for(j=n-1;j>=0;j--){
            if(B[j]!=A[i+j]){
                break;
            }
        }
        //如果全部比完，说明完全匹配
        if(j<0){
            return i;
        }else{
            //计算坏字符规则和好后缀规则需要移动的步数，选择较大值
            int x=j-bad_table[A[i+j]];
            int y=0;
            if(j<n-1){
                y=getGSMove(suffix,prefix,j,n);
            }
            i+=max(x,y);
        }
    }
    return -1;
}

17.4 Sunday算法

字符串匹配——Sunday算法和Sunday算法
Sunday算法由Daniel M.Sunday在1990年提出，它的思想跟BM算法很相似：1
只不过Sunday算法是从前往后匹配，在匹配失败时关注的是主串中参加匹配的最末位字符的下一位字符。

• 如果该字符没有在模式串中出现则直接跳过，即移动位数 = 模式串长度 + 1；

• 否则，其移动位数 = 模式串长度 - 该字符最右出现的位置(以0开始) = 模式串中该字符最右出现的位置到尾部的距离 + 1。 ```cpp int Sunday(string A,string B){ int m=A.length(),n=B.length(); //next数组存放不匹配的字符index vector next(SIZE,-1); for(int i=0;i<n;i++){

    next[B[i]]=i;

  }

  int i=0,j,k; while(i<=m-n){

    j=i;
    k=0;
    while(j<m && k<n && A[j]==B[k]){
        j++;k++;
    }
    //全部遍历完，说明匹配
    if(k==n){
        return i;
    }
    //不匹配，移动
    if(i+n<m){
        i+=(n-next[A[i+n]]);
    }else{
        break;
    }
  

  } return -1; }

<a name="n5lEa"></a>
#### 17.5 KMP算法
[字符串匹配的KMP算法-阮一峰](https://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html)<br />一个基本事实是，当空格与D不匹配时，你其实知道前面六个字符是"ABCDAB"。KMP算法的想法是，设法利用这个已知信息，不要把"搜索位置"移回已经比较过的位置，继续把它向后移，这样就提高了效率。<br />针对搜索词，算出一张《部分匹配表》（Partial Match Table）："前缀"和"后缀"。
```cpp
//假设在next[j]已经求得的情况下，若子串中字符tj等于ti，j为当前t最长相等前后缀长度，则next[i+1] = j+1
//若tj不等于ti,类似于失配时，移动子串，即j = next[j]
void getNext(string B,vector<int>& next){
    int n=B.length();
    next.resize(n);
    next[0]=-1;
    int i=0,j=-1;
    while(i<n){
        if(j==-1||B[i]==B[j]){
            next[++i]=++j;
        }else{
            j=next[j];
        }
    }

}
/**
 * @brief KMP算法
 * 部分匹配表
 * @param A 
 * @param B 
 * @return int 
 */
int KMP(string A,string B){    
    int m=A.length(),n=B.length();
    vector<int> next(n);
    getNext(B,next);
    int i=0,j=0;
    while(i<m && j<n){
        if(A[i]==B[j] || j==-1){
            //同时往下一个字符
            i++;j++;
        }else{            
            //搜索词后移next[j]个长度
            j=next[j];
        }
    }
    if(j==n){
        return i-j;
    }
    return -1;
}

DP算法
KMP 算法永不回退txt的指针i，不走回头路（不会重复扫描txt），而是借助dp数组中储存的信息把pat移到正确的位置继续匹配，时间复杂度只需 O(N)，用空间换时间，所以可以认为它是一种动态规划算法。
要确定状态转移的行为，得明确两个变量，一个是当前的匹配状态，另一个是遇到的字符；
影子状态：就是和当前状态具有相同的前缀。
KMP 算法就是要尽可能少的回退

//动态规划算法
int KMP_DP(string A,string B){
    int m=A.length(),n=B.length();
    //dp[状态][字符]=下个状态
    vector<vector<int>> dp(n,vector<int>(256));
    //base case
    dp[0][B[0]]=1;
    //影子状态X初始为0j
    int X=0;
    //构造状态转移图
    for(int j=1;j<n;j++){
        for(int c=0;c<256;c++){
            if(B[j]==c){
                //状态推进
                dp[j][c]=j+1;
            }else{
                //状态重启，返回影子状态，可以回退最少步数
                dp[j][c]=dp[X][c];
            }
        }
        //更新影子状态
        X=dp[X][B[j]];
    }

    int j=0;
    for(int i=0;i<m;i++){
        //计算A的下一个状态
        j=dp[j][A[i]];
        //到达终止态，返回结果
        if(j==n){
            return i-n+1;
        }
    }
    return -1;
}

17.6 Trie树

Trie树-帅地玩编程
Trie [traɪ] 读音和 try 相同，它的另一些名字有：字典树，前缀树，单词查找树等。
应用场景

1. Google、Baidu 等搜索引擎的搜索提示
2. 代码自动补全
3. IP路由查询使用的最长前缀匹配算法

Trie 是一颗非典型的多叉树模型， Trie 的结点是这样的：

struct TrieNode {
    bool isEnd; //该结点是否是一个串的结束
    TrieNode* next[26]; //字母映射表
};

性质

1. Trie 的形状和单词的插入或删除顺序无关，也就是说对于任意给定的一组单词，Trie 的形状都是唯一的。
2. 查找或插入一个长度为 L 的单词，访问 next 数组的次数最多为 L+1，和 Trie 中包含多少个单词无关。
3. Trie 的每个结点中都保留着一个字母表，这是很耗费空间的。如果 Trie 的高度为 n，字母表的大小为 m，最坏的情况是 Trie 中还不存在前缀相同的单词，那空间复杂度就为 O(m^n)。

时间复杂度
一次建树，多次查询
如果要在一组字符串中，频繁地查询某些字符串，用 Trie 树会非常高效。

• 构建 Trie 树的过程，需要扫描所有的字符串，时间复杂度是 O(n)（n 表示所有字符串的长度和）。

• 构建好 Trie 树后，在其中查找字符串的时间复杂度是 O(k)，k 表示要查找的字符串的长度。 ```cpp //Trie树 class Trie{ public: bool isEnd; Trie* next[26]; //插入，从根节点的子节点开始匹配，一直到前缀链上没有，就开辟新节点。 void insert(const string& word){

    Trie* node=this;
    for(char c:word){
        if(node->next[c-'a']==NULL){
            node->next[c-'a']=new Trie();
        }
        node=node->next[c-'a'];
    }
    node->isEnd=true;
  

  } //从根节点的子节点开始一直往下匹配，如果节点值为空返回0，匹配到最后判断isEnd bool search(const string& word){

    Trie* node=this;
    for(char c:word){
        node=node->next[c-'a'];
        if(node==NULL){
            return false;
        }
    }
    return node->isEnd;
  

  } //前缀匹配，从根节点的子节点开始一直往下匹配，如果节点值为空返回0，匹配到最后返回1 bool prefixMatched(const string& word){

    Trie* node=this;
    for(char c:word){
        node=node->next[c-'a'];
        if(node==NULL){
            return false;
        }
    }
    return true;
  

  }

  void deleteString(const string& word){

    //先找有没有
    if(!search(word)){
        return;
    }
    Trie* node=this;
    deleteWord(node,word,0);
  

  } //删除node所在结点，这个节点的子节点都为空或当前节点不是其他单词的结束结点才能删除 //首先找到word的最后一个字符 void deleteWord(Trie*& node,const string& word,int d){

    //长度上判断是不是最后一个字符
    if(d==word.length()){
        node->isEnd=false;
    }
    //不是的话，递归进入word的下一个字符
    else{
        deleteWord(node->next[word[d]-'a'],word,d+1);
    }
    //是其他单词的结束节点，不能删除
    if(node->isEnd){
        return;
    }
    //子节点不为空，不能删除
    for(Trie* item:node->next){
        if(node!=NULL){
            return;
        }
    }
    delete node;
    node=NULL;
  

  } };

void TrieTest(){ Trie t; t.insert(“tree”); t.insert(“tea”);

cout<<"Finding tree:"<<t.search("tree")<<endl;
cout<<"Finding prefix of te："<<t.prefixMatched("te")<<endl;
cout<<"Deleting tree:"<<endl;
t.deleteString("tree");
cout<<"Finding tree:"<<t.search("tree")<<endl;
cout<<"Finding prefix of te："<<t.prefixMatched("te")<<endl;

}

<a name="mJZB0"></a>
#### 17.7 [208. 实现 Trie (前缀树)](https://leetcode-cn.com/problems/implement-trie-prefix-tree/)
```cpp
class Trie {
public:
    Trie():next(26),isEnd(false) {
    }

    void insert(string word) {
        Trie* node=this;
        for(char c:word){
            if(node->next[c-'a']==NULL){
                node->next[c-'a']=new Trie();
            }
            node=node->next[c-'a'];
        }
        node->isEnd=true;
    }

    bool search(string word) {
        Trie* node=this;
        for(char c:word){
            node=node->next[c-'a'];
            if(node==NULL){
                return false;
            }
        }
        return node->isEnd;
    }

    bool startsWith(string prefix) {
        Trie* node=this;
        for(char c:prefix){
            node=node->next[c-'a'];
            if(node==NULL){
                return false;
            }
        }
        return true;
    }

    bool isEnd;
    vector<Trie*> next;
};

/**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * bool param_2 = obj->search(word);
 * bool param_3 = obj->startsWith(prefix);
 */

17.8 AC自动机

AC自动机(Aho-Corasick automaton)是用来处理多模式匹配问题的。
基本可认为是TrieTree+KMP。其中KMP是一种单模式匹配算法。
AC自动机的构造要点是失败指针的设置，用于匹配失败时跳转到另一节点继续匹配。同时在匹配的过程中也用来检索其他“同尾”的模式。
AC自动机
AC 自动机是 以 TRIE 的结构为基础 ，结合 KMP 的思想 建立的。
简单来说，建立一个 AC 自动机有两个步骤：

1. 基础的 TRIE 结构：将所有的模式串构成一棵 T r i e TrieTrie 。
2. KMP 的思想：对 T r i e TrieTrie 树上所有的结点构造失配指针。

然后就可以利用它进行多模式匹配了。
字典树构建
AC 自动机在初始时会将若干个模式串丢到一个 TRIE 里，然后在 TRIE 上建立 AC 自动机。这个 TRIE 就是普通的 TRIE，该怎么建怎么建。
TRIE 中的结点表示的是某个模式串的前缀。我们在后文也将其称作状态。一个结点表示一个状态，TRIE 的边就是状态的转移。
形式化地说，对于若干个模式串 s1,s2,s3….sn ，将它们构建一棵字典树后的所有状态的集合记作 Q 。
失配指针
AC 自动机利用一个 fail 指针来辅助多模式串的匹配。
状态 u 的 fail 指针指向另一个状态 v，其中 v ∈ Q ，且 v 是 u 的最长后缀（即在若干个后缀状态中取最长的一个作为 fail 指针）。对比 fail 指针与 KMP 中的 next 指针：

1. 共同点：两者同样是在失配的时候用于跳转的指针。
2. 不同点：next 指针求的是最长 Border（即最长的相同前后缀），而 fail 指针指向所有模式串的前缀中匹配当前状态的最长后缀。

因为 KMP 只对一个模式串做匹配，而 AC 自动机要对多个模式串做匹配。有可能 fail 指针指向的结点对应着另一个模式串，两者前缀不同。
AC 自动机在做匹配时，同一位上可匹配多个模式串。
构建指针
下面介绍构建 fail 指针的 基础思想
构建 fail 指针，可以参考 KMP 中构造 Next 指针的思想。
考虑字典树中当前的结点 u ， u 的父结点是 p ， p通过字符 c 的边指向 u ，即 trie[p,c]=u 。假设深度小于 u 的所有结点的 fail 指针都已求得。

1. 如果trie[fail[p],c] 存在：则让 u 的 fail 指针指向trie[fail[p],c] 。相当于在 p 和fail[p]后面加一个字符 c ，分别对应 u 和fail[u]。
2. 如果trie[fail[p],c]不存在：那么我们继续找到trie[fail[fail[p]],c] 。重复 1 的判断过程，一直跳 fail 指针直到根结点。
3. 如果真的没有，就让 fail 指针指向根结点。
4. 如此即完成了fail[u]的构建。 ```cpp class AcNode { public: char data; //该节点所存储的字符 bool isEnding = false; //是否结尾 vector children; //子节点 int length = -1; //长度 AcNode* fail = nullptr; //失配指针

public: AcNode(char data) { this->data = data; children.resize(26); } };

class Ac { public: //构建Trie树 void insert(string text) { AcNode* p = root; for (int i = 0; i < text.size(); ++i) { int index = text[i] - ‘a’; if (p->children[index] == nullptr) { p->children[index] = new AcNode(text[i]); } p = p->children[index]; } p->isEnding = true; p->length = text.size(); }

//建立失配指针，BFS
void buildFail() {
    queue<AcNode*> q;
    q.push(root);
    while (!q.empty()) {
        AcNode* p = q.front();

        q.pop();
        for (int i = 0; i < 26; ++i) {
            AcNode* pc = p->children[i];

            if (pc == nullptr) {
                continue;
            }

            if (p == root) {
                pc->fail = root;
            }
            else {
                AcNode* pp = p->fail;
                while (pp != nullptr) {
                    AcNode* ppc = pp->children[pc->data - 'a'];
                    if (ppc != nullptr) {
                        pc->fail = ppc;
                        break;
                    }
                    pp = pp->fail;
                }
                if (pp == nullptr) {
                    pc->fail = root;
                }
            }
            q.push(pc);
        }
    }
}
//KMP
void match(string text) {
    int n = text.size();
    AcNode* p = root;
    for (int i = 0; i < n; ++i) {
        int index = text[i] - 'a';
        while (p->children[index] == nullptr && p != root) {
            p = p->fail;
        }
        p = p->children[index];
        if (p == nullptr) p = root;
        AcNode* tmp = p;
        while (tmp != root) {
            if (tmp->isEnding) {
                int pos = i - tmp->length + 1;
                cout << "start : " << pos << "; len : " << tmp->length << endl;
            }
            tmp = tmp->fail;
        }
    }
}
void print() {
    cout << root->data << endl;

}

private: AcNode* root = new AcNode(‘1’); };

void ACTest(){ cout << “———————start———————“ << endl; Ac ac; ac.insert(“abc”); ac.insert(“as”); ac.insert(“afg”); ac.insert(“cd”); ac.insert(“ba”); ac.insert(“dfg”);

cout << "--------------------insert end ------------------" << endl;

ac.buildFail();

cout << "--------------------build end ------------------" << endl;

ac.match("abcdfg");

cout << "---------------end---------------" << endl;

} ```