https://codeforces.com/problemset/problem/149/E

题意：

已知一个长字符串S和一组询问字符串，对于每个询问需要知道在S中是否存在两个位置不同的子串可以组成该询问字符串。

题解：

正串后缀自动机树 + 反串后缀自动机树

考虑对 字符串S 的正串和反串分别建后缀自动机树.

将 询问字符串p 的正串在正串的 SAM 上去匹配，一直匹配到匹配不了为止，并记录 p[i] 在正串自动机节点上 endpos 的最小值 a[i]，即p[i]在S中的位置.

对 p 的反串也进行相同的处理，记录endpos 的最大值 b[i]，即p[i]在S中的位置.

我们只需枚举 1至length(p) 并判断 a[i] && b[i+1] && a[i]<b[i+1]  即可.

如果满足这个条件，就说明这个询问是有解的.

要注意判断一下长度为 1 的情况，这显然是无解的.