字典树、kmp、exkmp

一、字符串相关知识

1、字串：连续区间的串

2、子序列：可以不连续的串，但是相对位置要保持一致

3、sprintf、sscanf（对char类型而言）

4、string

append(s, pos, n) // 将字符串 s 中，从 pos 开始的 n 个字符连接到当前字符串结尾。
replace(pos, n, s) //删除从 pos 开始的 n 个字符，然后在 pos 处插入串 s。
erase(pos, n) // 删除从 pos 开始的 n 个字符。
insert(pos, s) // 在 pos 位置插入字符串 s。

二、字典树（Trie树）

1、字典树应用

• 查找字符串是否在字典树中出现
• 维护异或极值
• 维护异或和
• 全局加一

2、字典树相关代码

const int N = 1e5 + 10;
struct node{
    int cnt[10];//表示每个儿子节重复次数
    int nx[10];//表示儿子节点的编号
}a[N];
int n, tot;
string st[N];
int tt;

void add(string st){//向字典树中添加字符串st
    int now = 0;
    for(int i = 0; i < st.size(); i++){
        int ch = st[i] - '0';
        if(!a[now].nx[ch]){
            a[now].nx[ch] = ++tot;
        }
        a[now].cnt[ch] ++;
        now = a[now].nx[ch];
    }
}

bool fid(string st){//判断字典树是否含有st字符串
    int now = 0; 
    int ch;
    for(int i = 0; i < st.size(); i++){
        ch = st[i] - '0';
        if(i == st.size() - 1){
            if(a[now].cnt[ch] >= 2) return false;
        }
        now = a[now].nx[ch];
    }
    return true;
}