【算法】字符串

基本操作

c 中读取字符的函数为 getchar() ，他会读取任意单个输入的字符，用法 char ch; ch = getchar()。读取字符串的函数为 gets() 和 cin.getline()，它允许输入的字符串中存在空格，但不允许存在回车，因为gets()不会检查缓冲区溢出，所以是不安全的，在 C11 标准中已经被移除，getline()是 c++ 中的方法，相对安全。

一些常用的 string 类的库函数

1
2
3
4
5
6
7
8
9
10
#include<string>
using namespace std;
string str = "you are us";
//查找字符串
if((pos = str.find("you"))!=-1){
    cout>>strlen(str); // 返回长度
} 
string s("12345asdf");
//获得字符串s中从第0位开始的长度为5的字符串
string a = s.substr(0,5);

字典树

字典树是一个树形数据结构，以模拟字典的形式查找字符串，字典树常用于搜索引擎，代码补全，搜索补全，词频统计等领域

使用先序遍历来匹配给定字符串进行查询，插入、查询复杂度都是$O(m)$，$m$为字符串长度，有公共前缀的字符串可以一起存，节约了内存空间。

例题

后面的一连串提问，就是前缀匹配的问题，可以使用字典树去解决，为这些单词共同维护一个字典，然后在查询前缀的时候，返回终点后的叶子节点数，就能获得前缀单词的数量。

有个小细节就是，每次插入的过程中，对于同一前缀的词，他都一定会经过前缀的最后一个字符节点，每次经过就让那个字符节点的叶子数+1，就不用每次去遍历获取叶子节点了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<iostream>
#include<string>
using namespace std;
const int maxn = 5e5+10;
const int charsize = 26;
int nxt[maxn+1][charsize]; //字典树
int total[maxn+1]; //记录叶子节点数
int cnt = 0;

void insert(char s[],int len){
    int now = 0;
    for(int i=0;i<len;i++){
        int x = s[i] - 'a';
        if(!nxt[now][x]){
            nxt[now][x] = ++cnt;
        }
        now = nxt[now][x];
        total[now]++; //说明有一个单词经过了这个前缀，计数
    }
}

int search(char s[],int len){
    int now = 0;
    for(int i=0;i<len;i++){
        int x = s[i] - 'a';
        if(!nxt[now][x]){
            return 0;
        }
        now = nxt[now][x];
    }
    return total[now];
}

int main(){
    char str[11];
    while(cin.getline(str)){
        int len = strlen(str);
        if(!len) break;
        insert(str,len);
    }
    while(cin,getline(str)){
        cout<<search(str,strlen(str))<<endl;
    }
}

KMP算法

KMP 算法是一个单模式匹配算法，是目前能够达到的最优的模式匹配算法，它的算法复杂度为 $O(m+n)$，其中$m$为匹配字符串长度，$n$为待匹配字符串长度。

KMP 算法分为两个核心步骤：

  1. 找到匹配字符串的最大公共前后缀，计算 next 数组
  2. 按照 next 数组跳转进行模式匹配

计算 next 数组

简单上来讲，就是找最大的公共前后缀，然后由前缀部分跳转到后缀部分，整个 next 数组就是开一个数组去记录当匹配到了当前字符时，如果出现失配，应该从开头跳转到哪个字符。

求 next 数组，先从左往右遍历这个数组，然后去计算当前位置的最大公共前后缀，然后计算当前位的下一个位的 next 值（即要拿哪一位和下一位进行比较），如下图中，i=5 对应的最大公共前后缀长度为 3(ABA)，那么假设下一位发生失配，就要拿前缀 ABA 的下一个字符 B 来匹配。
所以 $next[i+1]=index(B)=3$

思路比较简单，KMP 算法难就难在代码怎么写，求 next 数组可以看成是一个动态规划过程，因为现在的公共前后缀都是前面的公共前后缀加上来的，用下面这张图理解

如果当前的 next 配对上了，next[i+1] 直接加 1 就好，如果没配对上，就要找他上一次的最大前缀，然后再看能不能配对上，循环这个过程直到配对上了或者回到了起点。

例题

以这道例题给 KMP 算法的标程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<iostream>
#include<string>
using namespace std;
string p,s;
int nxt[1000010];
int main(){
    cin>>s>>p;
    nxt[0],nxt[1]=0; //初始化
    int j=0; //用来记录目前到了哪一组最大前后缀
    for(int i=1;i<p.size();i++){
        // 如果没配对上，就找上一组，看看能不能配对上
        while(j && p[i]!=p[j]) j = nxt[j];
        // 如果配对上了，就+1，没配对上就赋值 0
        nxt[i+1] = (p[i]==p[j]) ? ++j:0;
    }
    j = 0; //j为匹配串的位置
    for(int i=0;i<s.size();i++){
        // 失配了，根据 next 数组跳转
        while(j && s[i]!=p[j]) j = nxt[j];
        j+=(s[i]==p[j])? 1 : 0; //如果匹配上了就加 1
        if(j==p.size()){
            cout<<i-p.size()+2<<endl;
        }
    }
    for(int i=1;i<=p.size();i++){
        cout<<nxt[i];
    }
}

在这个代码中 j = nxt[j] 就会将上一组最大前缀要匹配的下一个字符的下标赋给 j，也就是下图中的 3