【校招VIP】字符串算法合集- 校招VIP

转载声明：文章来源https://blog.csdn.net/weixin_45720782/article/details/109150240

说到字符串算法我们最先想到的就是模式匹配问题，所谓模式匹配就是字符串匹配问题，就是在一个长的主串中寻找子串的过程，如果我们直接暴力匹配那就是最基本的BF算法，也就是从主串的第一个字符和子串的第一个字符匹配，如果配对成功二者都继续比较后继的字符，否则子串从头开始，主串从第二个字符开始，一步步重复上述过程，直到配对成功或者到主串尾结束，这种算法有点靠天的感觉，如果运气好了，每一次主串和子串不匹配的时候都是第一个字符就不匹配，那么时间复杂度就是O(n+m),那还可以，但如果运气不好的话，每次主串和子串不成功的匹配都发生在子串T的最后一个字符的位置如主串S为“aaaaaaaaab”子串T为“aaab”这样时间复杂度就变成了O(n*m)，那就非常不友好了，如果我们对BF算法进行优化就变成了KMP算法，下面我详细的介绍一下KMP算法

KMP算法与BF算法最大的区别区别就是主串不进行回溯，BF算法每次匹配失败，主串回溯到上一次匹配的下一个字符，而KMP算法就不进行回溯，这里我们引入了一个数组，对子串进行一个BF，就是对相同的模式进行跟主串进行配对，具体可以通过一个例子整明白这个过程，这里面借用一下这三张图，因为觉得这三张图讲的还是非常清楚的。

当你求出了 next 数组之后，KMP 算法就很轻易搞定了，下面我用三张图，让你明白 KMP 算法完成匹配的整个过程。
以目标串：s，指针为 i ；模式串：t 指针为 j ; 为例

上图表示：“si-j ~ si-1” == “t 0 ~ t j-1”，s i != t j（前面都相等，但比较到 t j 时发现不相等了）且next[j] == k。

根据 next 数组的定义得知 “t k ~ t j-1” == “t 0 ~ t k-1”，所以 “t 0 ~ t k-1” == “si-k ~ si-1”

KMP具体的代码

int KMP(String s,String t)
{
   int next[MaxSize],i=0;j=0;
   Getnext(t,next);
   while(i<s.length&&j<t.length)
   {
      if(j==-1 || s[i]==t[j])
      {
         i++;
         j++;
      }
      else j=next[j];               //j回溯
   }
   if(j>=t.length)
       return (i-t.length);         //匹配成功，返回子串的位置
   else
      return (-1);                  //没找到
}

下面介绍另一个字符串的算法Trie字典树

这种算法顾名思义，也就是字母树，就是将每一个字符串存在这棵树中，树的每一个结点恰好对应一个字符，每个顶点代表从根到该结点的路径所对应的字符串，Trie字典树最大的有点就是利用了字符串的公共前缀，这样极大的节约了空间，典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串）用一个具体的实例来理解Trie字典树怎么存储字符串，这棵树中分别存储了abcd，abd，bcd，efg，hi这些字符串。

具体的代码实现如下

#include<cstdio>
#include<cstdlib>
using namespace std;
char s[11];
struct Trie{
    Trie* next[26];          //结构体指针 有26种字符
    int sum;                //单词出现的次数
    Trie(){                    //构造函数 便于初始化
        for(int i=0;i<26;i++){             //初始化
            next[i]=NULL;        //初始时，每个字符所对应数组下标中的指针为空
        }
        sum=0;
    }
}root;
void insert(char* s)   //创建字典树 在字典树上插入结点
{
    Trie* p=&root;            //从根结点开始遍历
    for(int i=0;s[i];i++){         //遍历单词的每一个字符
        if(p->next[s[i]-'a']==NULL){   //判断字符所对应结构体指针数组下标中的指针是否为空
            p->next[s[i]-'a']=new Trie;  //如果为空 就新建一个结点 
        }
        p=p->next[s[i]-'a'];   //将指针指向当前字符所对应的结构体指针数组的下标所对应的地址
        p->sum++;
    }
}
int find(char* s)        //查找单词
{
    Trie* p=&root;       //从根结点开始遍历
    for(int i=0;s[i];i++){      //遍历单词的每一个字符
        if(p->next[s[i]-'a']==NULL)return 0;   // 如果下标所对应的指针为空 查找失败
        else p=p->next[s[i]-'a'];   //如果不为空 遍历下一个字符 直至遍历结束
    }
    return p->sum;   //返回遍历完的最后一个结点中所对应的数据 代表当前当前单词出现的次数
}
int main(){
    while(gets(s)&&s[0]!='\0')             //读取字典中的单词 将其插入字典树中
        insert(s);
    while(scanf("%s",s)==1){           //在字典树中查找单词出现的次数
        printf("%d\n",find(s));
    }
    return 0;
}

另一个字符串算法就是基于KMP算法和Trie树的AC自动机

KMP算法是用来处理单模式串的问题，而AC自动机是用来处理多模式串的问题，也就是Trie树上的KMP，其实关于AC自动机我也没来及做很多题目进行训练，就是写了一下整个代码，把AC自动机实现了一下，这个过程明白了AC自动机的结构和实现方法，但是对于具体怎样去应用这个算法还没来及去做题感受。下面附上具体的代码实现，具体的应用我这两天多做几个题目补一下

#include <queue>
#include <cstdlib>
#include <cmath>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn =  2*1e6+9;
 
int trie[maxn][26]; //字典树
int cntword[maxn];  //记录该单词出现次数
int fail[maxn];     //失败时的回溯指针
int cnt = 0;
 
void insertWords(string s){
    int root = 0;
    for(int i=0;i<s.size();i++){
        int next = s[i] - 'a';
        if(!trie[root][next])
            trie[root][next] = ++cnt;
        root = trie[root][next];
    }
    cntword[root]++;      //当前节点单词数+1
}
void getFail(){
    queue <int>q;
    for(int i=0;i<26;i++){      //将第二层所有出现了的字母扔进队列
        if(trie[0][i]){
            fail[trie[0][i]] = 0;
            q.push(trie[0][i]);
        }
    }
 
//fail[now]    ->当前节点now的失败指针指向的地方
tire[now][i] -> 下一个字母为i+'a'的节点的下标为tire[now][i]
    while(!q.empty()){
        int now = q.front();
        q.pop();
 
        for(int i=0;i<26;i++){      //查询26个字母
            if(trie[now][i]){
                //如果有这个子节点为字母i+'a',则
//让这个节点的失败指针指向(((他父亲节点)的失败指针所指向的那个节点)的下一个节点)
                //有点绕,为了方便理解特意加了括号
 
                fail[trie[now][i]] = trie[fail[now]][i];
                q.push(trie[now][i]);
            }
            else//否则就让当前节点的这个子节点
                //指向当前节点fail指针的这个子节点
                trie[now][i] = trie[fail[now]][i];
        }
    }
}
 
 
int query(string s){
    int now = 0,ans = 0;
    for(int i=0;i<s.size();i++){    //遍历文本串
        now = trie[now][s[i]-'a'];  //从s[i]点开始寻找
        for(int j=now;j && cntword[j]!=-1;j=fail[j]){
            //一直向下寻找,直到匹配失败(失败指针指向根或者当前节点已找过).
            ans += cntword[j];
            cntword[j] = -1;    //将遍历国后的节点标记,防止重复计算
        }
    }
    return ans;
}
 
int main() {
    int n;
    string s;
    cin >> n;
    for(int i=0;i<n;i++){
        cin >> s ;
        insertWords(s);
    }
    fail[0] = 0;
    getFail();
    cin >> s ;
    cout << query(s) << endl;
    return 0;
}