NOIAC1755 Trie

题目大意

给定一个字典(字符串的集合), 有若干次询问, 每次询问给出一个文本串 \(S\), 需要回答 \(S\) 是否有某个子串与字典内的某个单词(字符串)同构.
一个串 \(S\) 与一个串 \(T\) 同构, 首先需要 \(|S|=|T|\), 并且存在一个关于字符集的双射 \(f\) 使得 \(S_i = f(T_i)\).
比如 \(ABB\) 和 \(XYY, BAA, TSS\) 同构, 但不和 \(AAB, XXY, ZZZ\) 同构.

数据范围

\(N \le 10^5, M \le 5 \times 10^5\)

解题思路

首先有个暴力的思路，即枚举每个子串，然后分配为字典序最小的串，哈希匹配一下即可。

容易发现复杂度瓶颈在枚举子串而且不好优化。因此我们考虑如何用 AC 自动机来完成匹配的过程。

我们可以记录每个字符当前位置和上一个出现位置的差，如果两个字符串的这个数组相同，即可认定两个字符串同构。因为字符集比较大，因此我们用 map 存暴力跳 fail 即可。另外要注意匹配时如果长度比上一个位置的差还要短，那么我们自动把它变为 i 即可，也就是匹配前缀是我们把 i 和 更大的数看成一个即可。

代码

/*
　　　　　／＞　 フ
　　　　　| 　_　 _|
　 　　　／`ミ _x 彡
　　 　 /　　　 　 |
　　　 /　  ヽ　　 ?
　／￣|　　 |　|　|
　| (￣ヽ＿_ヽ_)_)
　＼二つ
 */

#include 
#include 
#include 
#include 
#include 
#include 
#define MP make_pair
#define ll long long
#define fi first
#define se second
using namespace std;

template 
void read(T &x) {
    x = 0; bool f = 0;
    char c = getchar();
    for (;!isdigit(c);c=getchar()) if (c=='-') f=1;
    for (;isdigit(c);c=getchar()) x=x*10+(c^48);
    if (f) x=-x;
}

template
inline void write(F x, char ed = '\n') {
    static short st[30];short tp=0;
    if(x<0) putchar('-'),x=-x;
    do st[++tp]=x%10,x/=10; while(x);
    while(tp) putchar('0'|st[tp--]);
    putchar(ed);
}

template 
inline void Mx(T &x, T y) { x < y && (x = y); }

template 
inline void Mn(T &x, T y) { x > y && (x = y); }

#include