AC自动机(Trie图)模板

const int N = 1e6 + 5;
//tr就是多个模式串构造的fail树
//cnt标记该位置上有无单词
//id[i]:第i个模式串结尾所在的下标
int tr[N][26], idx = 1,nex[N], q[N],cnt[N],id[N];
char s[N];

void insert(int x)//字典树中插入字符串
{
    int p = 0;
    int len = strlen(s + 1);
    for (int i = 1; i <= len; i++)
    {
        int t = s[i] - 'a';
        if (!tr[p][t])
            tr[p][t] = idx++;
        p = tr[p][t];
    }
    cnt[p] = 1;
    id[x] = p;
}

/*
*	作用:构造多个模式串nex数组即fail树
*	时间复杂度:O(插入的字符的总长度)
*/
void build()
{
    int hh = 1, tt = 0;
    for (int i = 0; i < 26; i++)
        if (tr[0][i])
            q[++tt] = tr[0][i];

    while (hh <= tt)
    {
        int t = q[hh++];
        for (int i = 0; i < 26; i++)
        {
            //注意下面要改变tr[t][i]值，所以这里为了方便，直接引用
            int &p = tr[t][i];
            if (!p)
                p = tr[nex[t]][i];
            else
            {
                nex[p] = tr[nex[t]][i];
                q[++tt] = p;
            }
        }
    }
}

/*
*	作用:匹配
*	一般是通过文本串匹配多个模式串然后中途记一些数据
*	时间复杂度:O(n)
*/
for (int i = 1, j = 0; str[i]; i++)
{
    int t = str[i] - 'a' + 1;
    j = tr[j][t];

}