字符串板子

字典树

struct trie{
    int nxt[N][26], cnt = 0;
    bool vis[N]={0};//该节点结尾的字符串是否存在
    //int repeat[N] = {0};
    //两种重载版本
    void insert(string &s){
        int now = 0;
        for (int i = 0;i<s.size();++i){
            int tem = s[i] - 'a';
            if(!nxt[now][tem]) nxt[now][tem] = ++cnt;
            now = nxt[now][tem];
        }
        vis[now] = 1;
    }
    int find(string &s){
        int now = 0;
        for (int i=0;i<s.size();++i){
            int tem = s[i] - 'a';
            if(!nxt[now][tem]) return false;
            now = nxt[now][tem];
        }
        /*if(vis[now]){
            ++repeat[now];
        }   return repeat[now];*/
        return vis[now];
    }
};

前缀函数

需要注意的是，前缀函数本身就是”跳转“，需要注意这个跳转的失配函数性质。

int pre_len[N];
void pre_len_process(string s){
    //kmp:string s,string t;
    //string last=s+"#"+t;
    for(int i=0;i<s.size();++i){
        int j=pre_len[i-1];
        while(j>0&&s[i]!=s[j]){
            j=pre_len[j-1];
        }
        if(s[i]==s[j]){
            ++j;
        }
        pre_len[i]=j;
    }
}