icontofig | 发布于 2020-01-27 16:34:36 | 阅读量 604 | 字符串
发布于 2020-01-27 16:34:36 | 字符串
#include <bits/stdc++.h>
const int maxn = 2e5 + 5;
using namespace std;
struct Trie{
    int nex[maxn][26], fail[maxn], end[maxn];
    int root, p;
    inline int newnode() {
        for (int i = 0; i < 26; ++i) {
            nex[p][i] = -1;
        }
        end[p++] = 0;
        return p - 1;
    }
    inline void init() {
    	p = 0;
    	root = newnode();
    }
    inline void insert(char *buf) {
        int now = root;
        for (int i = 0; buf[i]; ++i) {
            if (nex[now][buf[i]-'a'] == -1) 
                nex[now][buf[i]-'a'] = newnode();
            now = nex[now][buf[i]-'a'];
        }
        end[now]++;
    } 
    inline void build() {
        queue<int> que;
        fail[root] = root;
        for (int i = 0; i < 26; ++i) {
            if (nex[root][i] == -1)
                nex[root][i] = root;
            else {
                fail[nex[root][i]] = root;
                que.push(nex[root][i]);
            }
        }
        while (!que.empty()) {
            int now = que.front();
            que.pop();
            for (int i = 0; i < 26; ++i) {
                if (nex[now][i] == -1) 
                    nex[now][i] = nex[fail[now]][i];
                else {
                    fail[nex[now][i]] = nex[fail[now]][i];
                    que.push(nex[now][i]);
                }
            }
        }
    }
}L, R;



内容更新于: 2020-01-27 16:34:36
链接地址: http://blog.leanote.com/post/icontofig/%E4%B8%80%E4%B8%AA%E7%9C%8B%E8%B5%B7%E6%9D%A5%E9%A3%9E%E5%BF%AB%E7%9A%84ACzi-zo

上一篇: luogu P4178 Tree 点分治+树状数组

下一篇: Educational Codeforces Round 80 (Rated for Div. 2) E Messenger Simulator 树状数组求区间内不同的数的个数

604 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航