字符串综合

字符串，一个我小时候学 python 就爱之入骨的数据类型
他的拼接什么的真的太方便啦！

字符串的相关定义

字符串，由若干字符组成的串。（以下知识可以类比集合）
记字符串为 $S$，其长度 $n$ 为 $|S|$
子串：字符串 $S$ 的连续的一段子字符串。
子序列：从字符串 $S$ 中提取若干个字符，保持原本的相对位置组成的序列，不要求连续。
前缀、后缀、回文串是常识。
字典序：类比字典，跟字典一样的排序方法。

C++的字符串

以前很爱用 char 数组，因为可以更简单实现下标从 $1$ 到 $n$
但现在发现 string 才是真神，快来用！！!
string 类型可以直接输入输出、比较，用 + 进行拼接，下标从 0 开始。

``` 和 ``` s.length() ``` 可以 $O(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
字符串的比较是 $O(|S|)$ 的，慎用
``` s1.find(s2) ``` 的复杂度是 $O(|S_1|·|S_2|)$
那查找的效率太低了，所以有了 KMP
## KMP
*你我不合，未必无用*
其中 b 数组表示 boader，即一个字符串里面最大的子串的长度，这个子串满足既是字符串的真前缀又是真后缀。我们能够 $O(|s|)$ 的求出 b 数组（这是最巧妙的地方），然后再用 b 数组 $O(|s_1|+|s_2|)$ 的查找。
```cpp
vector<int> prev(string s){ 
    int n=s.length();
    vector<int> b(n);
    for(int i=1;i<n;i++) {
        int j=b[i-1];
        while(j>0&&s[i]!=s[j]) j=b[j-1];
        if(s[i]==s[j]) j++;
        b[i]=j;
    }
    return b;
} 
vector<int> find(string s1,string s2){//返回的是出现的第一个字符的位置
    string s=s2+'@'+s1;
    int len1=s1.length(),len2=s2.length();
    vector<int> res,b=prev(s); 
    for(int i=len2+1;i<=len1+len2;i++)
        if(b[i]==len2) res.push_back(i-2*len2);
    return res; 
}

字典树 Trie

已经是带“树”字的数据结构里面最短的了。

使用场景

处理字符串集合，支持

  • 插入
  • 删除
  • 查询
  • 统计

时间复杂度 $O(|s|)$
map（$O(|s|\log n)$）: 所以是不爱我了吗
答：Trie 还可以前缀统计，排序输出，求第 k 大

模板

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
45
int getnum(char x){//字符转数字
    return x-'a'; 
    if(x>='A'&&x<='Z')
        return x-'A';
    else if(x>='a'&&x<='z')
        return x-'a'+26;
    else
        return x-'0'+52;
} 
struct Trie{
    int nxt[N][70],tot,cnt[N];
    void clean(){
        for(int i=0;i<=tot;i++)
            for(int j=0;j<70;j++) 
                nxt[i][j]=0,cnt[i]=0;
        tot=0;
    }
    void insert(string s){
        int pos=0;
        for(auto c:s){
            int x=getnum(c);
            if(nxt[pos][x]==0) nxt[pos][x]=++tot;
            pos=nxt[pos][x];
            ++cnt[pos]; //算前缀放这
        } 
        //只算字符串本身放这
    } 
    void del(string s){
        int pos=0;
        for(auto c:s){
            int x=getnum(c);
            pos=nxt[pos][x];
            if(--cnt[pos]==0) nxt[pos][x]=0; 
        } 
    } 
    int find(string s){
        int pos=0;
        for(auto c:s){
            int x=getnum(c);
            if(nxt[pos][x]) pos=nxt[pos][x];
            else return 0;
        }
        return cnt[pos]; 
    } 
}trie;