数据结构与算法

发布日期: 2021-09-10

文章字数: 3.9k

知识点整理（5）trie/kmp/ac自动机

本篇主要讲一些对字符串处理的好东西

Trie（前缀树/字典树）

每个结点包含一个字符（对于字符串问题来说）
一个结点所对应的字符串:从根到该节点的路径上所有字母依次连起来所组成的字符串。
根节点对应空字符串。
一个节点v的所有子孙有相同的前缀，即v对应的字符串。
是一个十分典型的以空间换时间的算法
典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高
插入查找的复杂度为$O(n)$，n为字符串长度。

基本思想（以字母树为例）

Insert（string key, int value）
对于一个单词，从根开始，沿着单词的各个字母所对应的树中的节点分支向下走，直到单词遍历完，将最后的节点标记为红色，表示该单词已插入Trie树。
Find（string key）
同样的，从根开始按照单词的字母顺序向下遍历trie树，一旦发现某个节点标记不存在或者单词遍历完成而最后的节点未标记为红色，则表示该单词不存在，若最后的节点标记为红色，表示该单词存在。
Delete（string key）
从trie中删除一个字符串key以及它的键值，只需将标志置为未标记即可，但同时要将所有以该字符串为公共前缀的字符串注销（一般不用进行删除操作）

模板实现：

class Trie {
public:
    Trie* children[60];//大小写字母
    bool isword=false;
    bool isprefix=false;
    /** Initialize your data structure here. */
    Trie() {
        memset(children,0,sizeof(children));
    }
    
    /** Inserts a word into the trie. */
    void insert(string word) {
        Trie*p=this;
        for(auto e:word){
            if(p->children[e-'A']==NULL)p->children[e-'A']=new Trie;
            p=p->children[e-'A'];
            p->isprefix=true;
        }
        p->isword=true;
    }
    
    /** Returns if the word is in the trie. */
    bool search(string word) {
        Trie*p=this;
        for(auto e:word){
            if(p->children[e-'A']==NULL)return false;
            p=p->children[e-'A'];
        }
        if(p==NULL||!p->isword)return false;
        return true;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix) {
        Trie*p=this;
        for(auto e:prefix){
            if(p->children[e-'A']==NULL)return false;
            p=p->children[e-'A'];
        }
        if(p==NULL||!p->isprefix)return false;
        return true;
    }
};

常见应用

字母序排序
问题描述：给定一些字符串，按字典序从小到大输出
解题思路：构建trie：每个结点的儿子按字母序排列。按先序遍历访问trie
词典
问题描述：假设有n个英文单词$w_1,…,w_n$.对每个单词$w_i$，有一个字符串为其中文翻译。如(‘apple’–‘苹果’)（‘banana’–‘香蕉’）。你需要写一个dictionary(词典）软件。用户输入一个串Q后，若Q=wi要输出wi的翻译。
解题思路：为$(w_1,…,w_n)$构造一个trie。$w_i$的键值设置为它的中文翻译。输入Q后，用O(|Q|)时间找到trie中对应Q的结点，输出其键值。
词频统计 & 关键词检测
单词自动提示功能
最长公共前缀
问题描述：给定一些单词$w_1,…,w_n$。接下来将给你一系列查询。每个查询的形式为(i,j)：表示你需要回答$w_i与w_j$的最长公共前缀的长度。
解题思路：从所有单词建立一个trie。wi与wj的最长公共前缀的长度即它们所在结点的公共祖先个数，于是，问题就转化为了最近公共祖先（Least Common Ancestor，简称LCA）问题。

给点好题

原题链接：洛谷P2580错误的点名开始了

直接上代码：

#include<bits/stdc++.h>
using namespace std;
int n, m;
class trienode{
public:
    trienode *child[26];
    bool isword;
    int count;//统计单词遍历次数
    trienode():count{0},isword{false}{
        memset(child, 0, sizeof(child));
    }
    void insert(string word){
        trienode *p = this;
        for(auto e:word){
            if(p->child[e-'a']==NULL)
                p->child[e - 'a'] = new trienode;
            p = p->child[e-'a'];
        }
        p->isword = true;
    }
    void search(string word){
        trienode *p = this;
        for(auto e:word){
            if(p->child[e-'a']==NULL){
                cout << "WRONG" << endl;
                return;
            }
            p = p->child[e-'a'];
        }
        if(p->isword){
            if(p->count==0){
                p->count++;
                cout << "OK" << endl;
            }
            else
                cout << "REPEAT" << endl;
        }
        else
            cout << "WRONG" << endl;
    }
};
int main(){
    trienode *root=new trienode;
    cin >> n;
    string temp;
    for (int i = 1; i <= n;i++){
        cin >> temp;
        root->insert(temp);
    }
    cin >> m;
    for (int i = 1; i <= m;i++){
        cin >> temp;
        root->search(temp);
    }
    return 0;
}

再来一道：洛谷P5149

先上代码：

#include<iostream>
#include<memory.h>
#include<string>
#define max_N 100010
using namespace std;
int n{0};
long long count{0};
int data_[max_N]{0};
class trienode{
public:
    trienode *children[60];
    int order;
    trienode(){
        memset(children, 0, sizeof(children));
    }
    void insert(string s,int o){
        trienode *p = this;
        for(auto e:s){
            if(p->children[e-'A']==NULL)
                p->children[e - 'A'] = new trienode;
            p = p->children[e-'A'];
        }
        p->order = o;
    }
    int search(string s){
        trienode *p = this;
        for(auto e:s){
            p = p->children[e - 'A'];
        }
        return p->order;
    }
};
void merge(int left,int mid,int right){
    int j = left, k = mid + 1,i=1;
    int temp[right - left + 2];
    while(j<=mid&&k<=right){
        if(data_[j]>data_[k]){
            temp[i++] = data_[k++];
            count+=mid-j+1;
        }
        else{
            temp[i++] = data_[j++];
        }
    }
    while(j<=mid){
        temp[i++] = data_[j++];
    }
        
    while(k<=right)
        temp[i++] = data_[k++];
    for (int m = 1; m < i;m++){
        data_[left + m - 1] = temp[m];
    }
}
void mergesort(int left,int right){
    if(left<right){
        int mid = (left + right) / 2;
        mergesort(left, mid);
        mergesort(mid + 1, right);
        merge(left, mid, right);
    }
}
trienode *root = new trienode;
int main(){
    cin >> n;
    string temp;
    for (int i = 1; i <= n;i++){
        cin >> temp;
        root->insert(temp,i);
    }
    for (int i = 1; i <= n;i++){
        cin >> temp;
        data_[i] = root->search(temp);
    }
    mergesort(1, n);
    cout << count << endl;
    return 0;
}

这道题主要考察的其实是归并排序的写法，trie树是一个用来存字符串原先顺序的工具，此题中的trie树可以用hashmap来替代，这里顺便讲一下trie树和哈希表的区别。两者都可以用来进行搜索，trie树常用于字符串查询，复杂度为$O(m)$，m为key的长度，哈希表查找的复杂度决定于冲突，最好是$O(1)$，最坏是$O(n)$。trie常用于模糊搜索，而哈希表常用于精确搜索，此题我认为用hashmap更为简单和快速。

KMP

先讲KMP要解决的问题：串的模式匹配，即寻找给定子串在主串中的位置。

BF算法

在讲KMP之前，我想讲讲解决这种问题的一种最朴素的算法，BF算法，这是一种带回溯的穷举算法，KMP实则就是在回溯这一点上进行了优化。

基础思想：对每个$i(0≤i≤n-m)$，检查$S[i+1,i+m]$是否为T。

若发现$S[i+1,i+m]$==T，匹配成功，返回 i+1。
如果以上全都不等于T则匹配失败，返回0。

代码实现：

=0; j=0;
while (i < n){
if (S[i+1] == T[j+1]){//这里串都是从1开始，S[0]不存数据，存个长度也行
	i++; j++;
	if (j==m) return i-m+1; //匹配成功
}
else{ i=i-j+1; j=0;} //下个检查的开始
}
return 0; //表示匹配失败

复杂度分析：最坏情况下，$(n-m+1) * m＝O((n-m)*m)$，此时从任何位置i开始，都检查到串T的最后一位！最好情况下，一配就中！只比较了m次。而平均情况下可证明为$O(m+n)$

KMP主过程

KMP的设计思路，主要是对于如何避免搜索主串时的不必要回溯。
设计时要思考哪些是不必要的回溯，此处引入前后缀，找到0~j-1中最大整数k使得$T[1,j]$的长为k的前、后缀相等。然后i不变，令j=k即可。

主过程代码如下：

i = j = 0;
while (i < n){
if (S[i+1] == T[j+1]){
    i++; j++; 
    if (j==m) return i – m + 1;
}
else if (j == 0) i++;  
   else j = pi[j];
}
return 0. //表示匹配失败

预处理FAILURE function

这里是要对所匹配的子串进行预处理，$pi[j]$=最大的(非负)整数k使得$T[1,k]$是$T[1,j]$的真后缀。

i=1; j = 0; pi[1] = 0;
while (i < m){
    if (T[i+1] == T[j+1]){
        pi[++i] = ++j;
    }
    else if (j == 0){
        pi[++i] = j;
    } else j = pi[j];
}

放道例题

找T的所有出现的KMP算法

代码实现：

#include <iostream>
using namespace std;
const int maxn =100;

int n, m, pos;
char S[maxn + 1], T[maxn + 1];
int pi[maxn+1],book[maxn+1]{0};

void compute_pi(){
  int i= 1, j = 0; pi[1] = 0;pi[0]=0;
  while (i < m){
    if (T[i] == T[j]){
    	i++;
    	j++;
    	pi[i]=j;
	}	  
    else if (j == 0)pi[++i]=0;
    else j = pi[j];
}
}

void string_Index(){
  int i = pos-1, j = 0;
  while (i < n){
	  if (S[i] == T[j]){
	  	i++;
		  j++;
      if(j==m){
        book[i - m + 1] = 1;
        j = pi[j];
      }
        //add something
	  }
    else{
      j=pi[j]; 
      i++;
    }
	  //add something
  }
}

int main(){
	scanf("%d", &n); getchar(); gets(S);
	scanf("%d", &m); getchar(); gets(T);
	scanf("%d", &pos);
	compute_pi();
  string_Index();
  for (int i = 1; i <= n-m+1;i++){
    if(book[i]!=0)
        cout << i << endl;
  }
  return 0;
}

我承认我KMP讲的并不好，（逃

AC自动机

给定n个模式串和1个文本串，求有多少个模式串在文本串里出现过。
看似这似乎跟KMP要解决的问题没啥区别，但是我们不可能整n个failure function。于是我们引进了AC自动机，它有点类似于“在trie树上进行KMP”。

先上模板题：洛谷P3808AC自动机模板（简单版）

算法实现：首先我们要用n个模式串建一颗trie树，然后用文本串在上面进行匹配。每次匹配时，都要检查一下当前结点及其前缀是否构成一个模式串。

当我们无法在继续往下匹配的时候，我们要回到根结点重新开始匹配，那肯定不行，那就太low了。此时我们要想起KMP的实现，我们可以回溯到某个结点在开始匹配。此时我们将引入失配指针（Fail）来帮助我们完成回溯的过程。

Fail: 如果一个点i的Fail指针指向j。那么root到j的字符串是root到i的字符串的能在trie树上找到的一个最长后缀。是不是有点眼熟？

注意点：

每一个点i的Fail指针指向的点的深度一定是比i小的。
第一层结点的Fail一定指的是root。
在代码中可以假设出0号节点，让root为1，而让0号结点的所有儿子都指向root，即trie[0].child[0~26]=1，这样可以让所有回溯到的0的都能回到根节点（其实不用也行）

关键点：

当前结点i的Fail的指向实则是由父亲结点的FaFail所决定的，其应指向fafail的与i值相等的儿子结点即trie[cur].fail=trie[trie[fa].fail].son[cur];
倘若当前结点i不存在怎么办，我们同样可以进行路径优化，将该节点直接等于fafail的对应值的儿子结点，即trie[fa].son[cur]=trie[tire[fa].fail].son[cur];，但注意不存在的不需要压入队列
由失配指针fail的处理，我们可以得知想要处理i结点就必须先处理i的父亲结点，所以我们可以一层层的来调配失配指针，即使用bfs。

getfail过程代码实现：

void get_fail(){
    for (int i = 0; i < 26;i++)
        trie[0].child[i] = 1;//0号结点的所有儿子都为root
    q.push(1);//root压入队列
    trie[1].fail = 0;//指向0
    while(!q.empty()){
        int u = q.front();//拿出队首结点，作为父亲节点
        q.pop();
        int f = trie[u].fail;//拿出fafail
        for (int i = 0; i < 26;i++){//遍历其所有儿子结点
            int v = trie[u].child[i];
            if(!v){//儿子结点如果不存在
                trie[u].child[i] = trie[f].child[i];//关键点2
                continue;//不要压入队列，快逃！
            }
            trie[v].fail = trie[f].child[i];//关键点1，可以发现如果此时f=0,其所有child都为1
            q.push(v);
        }
    }
}

查询过程：

查询就是不断跳fail嘛，毕竟fail是最长后缀，当前的如果可以匹配，那后缀当然也行，由于数据中存在重复单词，所以对于每个结点都有一个flag来进行计数，ans不断累加，并在累加后将flag置为-1，以避免重复叠加，跳fail的过程当跳回根节点或者跳到flag为-1的重复结点就结束。

int query(string s){
    int u = 1, ans = 0;
    for(auto e:s){
        int l = e - 'a';
        int k = trie[u].child[l];
        while(k>1&&trie[k].flag!=-1){
            ans += trie[k].flag;//累加计数
            trie[k].flag = -1;//避免重复 
            k = trie[k].fail;
        }
        u = trie[u].child[l];//跳trie
    }
    return ans;
}

放上完整代码：

 #include<bits/stdc++.h>
using namespace std;
typedef struct {
    int child[26]{0}, flag{0}, fail;
}trienode;
const int maxn = 1000010;
trienode trie[maxn];
queue<int> q;
int n,cnt{1};//cnt记几号结点
void insert(string s){
    int u = 1;
    for(auto e:s){
        int l = e - 'a';
        if(!trie[u].child[l])
            trie[u].child[l] = ++cnt;
        u = trie[u].child[l];
    }
    trie[u].flag ++;//重复字符串
}
void get_fail(){
    for (int i = 0; i < 26;i++)
        trie[0].child[i] = 1;
    q.push(1);
    trie[1].fail = 0;
    while(!q.empty()){
        int u = q.front();
        q.pop();
        for (int i = 0; i < 26;i++){
            int v = trie[u].child[i];
            int f = trie[u].fail;
            if(!v){
                trie[u].child[i] = trie[f].child[i];
                continue;
            }
            trie[v].fail = trie[f].child[i];
            q.push(v);
        }
    }
}
int query(string s){
    int u = 1, ans = 0;
    for(auto e:s){
        int l = e - 'a';
        int k = trie[u].child[l];
        while(k>1&&trie[k].flag!=-1){
            ans += trie[k].flag;
            trie[k].flag = -1;
            k = trie[k].fail;
        }
        u = trie[u].child[l];
    }
    return ans;
}
int main(){
    cin >> n;
    string temp;
    for (int i = 1; i <= n;i++){
        cin >> temp;
        insert(temp);
    }
    get_fail();
    cin >> temp;
    cout << query(temp);
    return 0;
}

加一道加强版：洛谷P3796ac自动机加强版

#include<bits/stdc++.h>
using namespace std;
typedef struct {
    int child[26]{0}, flag{0}, fail;
    void clear(){memset(child, 0, sizeof(child));fail=flag=0;}
}trienode;
const int maxn = 1000010;
trienode trie[maxn];
string s1[200];
int vision[200]{0};
queue<int> q;
int n,cnt{1},num{1};
void insert(string s){
    int u = 1;
    for(auto e:s){
        int l = e - 'a';
        if(!trie[u].child[l])
            trie[u].child[l] = ++cnt;
        u = trie[u].child[l];
    }
    trie[u].flag = num++;
}
void get_fail(){
    for (int i = 0; i < 26;i++)
        trie[0].child[i] = 1;
    q.push(1);
    trie[1].fail = 0;
    while(!q.empty()){
        int u = q.front();
        q.pop();
        for (int i = 0; i < 26;i++){
            int v = trie[u].child[i];
            int f = trie[u].fail;
            if(!v){
                trie[u].child[i] = trie[f].child[i];
                continue;
            }
            trie[v].fail = trie[f].child[i];
            q.push(v);
        }
    }
}
int query(string s){
    int u = 1;
    for(auto e:s){
        int l = e - 'a';
        int k = trie[u].child[l];
        while(k>1){
            if(trie[k].flag)
                vision[trie[k].flag]++;
            k = trie[k].fail;
        }
        u = trie[u].child[l];
    }
    return 0;
}
int main(){
    cin >> n;
    string temp;
    while(n!=0){
        int ans = 0;
        for (int i = 1; i <= n;i++){
            cin >> temp;
            s1[num] = temp;
            insert(temp); 
        }
        get_fail();
        cin >> temp;
        query(temp);
        for (int i = 1; i <= n;i++){
            ans = max(ans, vision[i]);
        }
        cout << ans << endl;
        for (int i = 1; i <= n;i++){
            if(vision[i]==ans)
                cout << s1[i] << endl;
        }
        for (int i = 0; i <= cnt;i++)
            trie[i].clear();
        cin >> n;
        num = cnt = 1;
        memset(vision, 0, sizeof(vision));
    }
    return 0;
}