LibreOJ 6583 「ICPC World Final 2019」何以伊名始

依然是一个广义 SAM 屑题（
于是 ACAM 照样能做（

为了符合各种字符串数据结构的习惯，考虑将所有串反过来。
发现将输入看做 Trie 上的连边就可以了。
于是直接 BFS 建广义 SAM，询问则将询问串反过来放在广义 SAM 上跑，达到的状态的 Parent Tree 上子树内所有状态都是以它为一个后缀的字符串。
又因为每个状态一定都是一个名字，所以直接对所有串维护 |endpos| 即可。

代码：

#include <cstdio>
#include <cstring>
using namespace std;
const int N = 1e6;
int n,m,k;
char s[N + 5];
struct node
{
    int ch[26];
    int ed;
} tr[N + 5];
namespace SAM
{
    struct node
    {
        int ch[26];
        int fa,len;
    } sam[(N << 1) + 5];
    int tot = 1,las = 1,sz[(N << 1) + 5];
    inline void insert(int x)
    {
        int cur = las,p = las = ++tot,nxt;
        sam[p].len = sam[cur].len + 1,sz[p] = 1;
        for(;cur && !sam[cur].ch[x];cur = sam[cur].fa)
            sam[cur].ch[x] = p;
        if(!cur)
            sam[p].fa = 1;
        else
        {
            int q = sam[cur].ch[x];
            if(sam[cur].len + 1 == sam[q].len)
                sam[p].fa = q;
            else
            {
                nxt = ++tot;
                sam[nxt] = sam[q],sam[nxt].len = sam[cur].len + 1,sam[p].fa = sam[q].fa = nxt;
                for(;cur && sam[cur].ch[x] == q;cur = sam[cur].fa)
                    sam[cur].ch[x] = nxt;
            }
        }
    }
    int c[N + 5],a[(N << 1) + 5];
    inline void init()
    {
        for(register int i = 1;i <= tot;++i)
            ++c[sam[i].len];
        for(register int i = 1;i <= N;++i)
            c[i] += c[i - 1];
        for(register int i = tot;i > 1;--i)
            a[c[sam[i].len]--] = i;
        for(register int i = tot;i > 1;--i)
            sz[sam[a[i]].fa] += sz[a[i]];
    }
}
int q[N + 5],head,tail;
int main()
{
    scanf("%d%d",&n,&k);
    char ch;
    int fa;
    for(register int i = 1;i <= n;++i)
        scanf(" %c%d",&ch,&fa),tr[++fa].ch[ch - 'A'] = i + 1;
    q[tail = 1] = 1,tr[1].ed = 1;
    for(register int p;head < tail;)
    {
        p = q[++head];
        for(register int i = 0;i < 26;++i)
            if(tr[p].ch[i])
                SAM::las = tr[p].ed,SAM::insert(i),tr[tr[p].ch[i]].ed = SAM::las,q[++tail] = tr[p].ch[i];
    }
    SAM::init();
    for(;k;--k)
    {
        scanf("%s",s + 1),m = strlen(s + 1);
        int p = 1,flag = 0;
        for(register int i = m;i;--i)
        {
            if(!SAM::sam[p].ch[s[i] - 'A'])
            {
                puts("0"),flag = 1;
                break;
            }
            p = SAM::sam[p].ch[s[i] - 'A'];
        }
        if(!flag)
            printf("%d\n",SAM::sz[p]);
    }
}