AC自动机

题目大意：
给定一个文本串$s$和$m$个模式串$t$，求每个模式串中，在$s$中出现过的前缀的长度的最大值。
例如$s="SNNSSNS"$，$t="NNN"$，在$s$中出现过的前缀有$"N","NN"$，其中最长的是$"NN"$，长度为$2$。
由于需要计算的是前缀，所以可以把某个模式串看做是多个它的前缀的模式串的合体。那如何存储这些模式串呢，提到了前缀，那绝配肯定就是$trie$树了。
接下来的目标是要查找每个模式串出现过的前缀的长度的最大值，显然是多模式匹配，所以上$AC$自动机，和模板没有什么区别，甚至不需要优化，但注意，每次加完$end$后都应该设为特殊标记(如$-1$)，代表这是找到过的，然后统计时只累加有标记的。

#include<bits/stdc++.h>
using namespace std;

int n,m,f[128],cnt;  // f:字符映射(E->0,S->1,W->2,N->3), cnt:Trie节点计数
string str[100005];  // 存储M个模式串
struct node
{
    int son[4],end,fail;  // son[4]:四个方向的子节点, end:结束标记(-1表示已访问), fail:AC自动机fail指针
} t[10000005];
inline int find(string s)
{
    int root=0,mx=0;  // root:当前Trie节点, mx:最大匹配长度
    for (int i=0;i<s.size();i++)
    {
        root=t[root].son[f[s[i]]];  // 沿着Trie树走
        if (t[root].end==-1)  // 如果当前节点被标记为已访问(说明母串匹配到此)
            mx=i+1;  // 更新最大匹配长度为当前前缀长度
    }
    return mx;
}
inline void build(string s,int id)
{
    int root=0;  // 从根节点开始插入
    for (auto c:s)
    {
        c=f[c];  // 字符转数字
        if (!t[root].son[c]) t[root].son[c]=++cnt;  // 创建新节点
        root=t[root].son[c];  // 移动到子节点
    }
    t[root].end++;  // 标记模式串终点(实际只关心是否>0)
}
inline void getfail()
{
    queue<int> q;
    for (int i=0;i<4;i++)  // 初始化队列:根节点的直接子节点
    {
        if (t[0].son[i])
            q.push(t[0].son[i]);
    }
    while (!q.empty())  // BFS构建fail指针
    {
        int now=q.front();
        q.pop();
        for (int i=0;i<4;i++)
        {
            if (t[now].son[i])  // 如果存在子节点
            {
                t[t[now].son[i]].fail=t[t[now].fail].son[i];  // 设置fail指针
                q.push(t[now].son[i]);  // 子节点入队
            }
            else  // 路径压缩:不存在子节点时直接指向fail指针的对应节点
                t[now].son[i]=t[t[now].fail].son[i];
        }
    }
}
inline void query(string s)
{
    int root=0;
    for (auto c:s)  // 遍历母串
    {
        root=t[root].son[f[c]];  // 在Trie上移动(可能通过路径压缩跳转)
        int i=root;
        while (i && t[i].end!=-1)  // 沿着fail链标记所有未访问的节点
            t[i].end=-1,i=t[i].fail;  // 标记为已访问并跳转fail指针
    }
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
    f['E']=0,f['S']=1,f['W']=2,f['N']=3;  // 建立字符映射表
    string s;
	cin >> n >> m >> s;  // 读入母串长度n,模式串数m,母串s
    for (int i=1;i<=m;i++)
    {
        cin >> str[i];
        build(str[i],i);  // 构建Trie树
    }
    getfail();  // 构建AC自动机fail指针
    query(s);  // 用母串匹配并标记所有出现的节点
    for (int i=1;i<=m;i++)
        cout << find(str[i]) << endl;  // 对每个模式串查询最大匹配前缀长度
	return 0;
}