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

題意：

已知一個長字符串S和一組詢問字符串，對于每個詢問需要知道在S中是否存在兩個位置不同的子串可以組成該詢問字符串。

題解：

正串后綴自動機(jī)樹 + 反串后綴自動機(jī)樹

考慮對 字符串S 的正串和反串分別建后綴自動機(jī)樹.

將 詢問字符串p 的正串在正串的 SAM 上去匹配，一直匹配到匹配不了為止，并記錄 p[i] 在正串自動機(jī)節(jié)點(diǎn)上 endpos 的最小值 a[i]，即p[i]在S中的位置.

對 p 的反串也進(jìn)行相同的處理，記錄endpos 的最大值 b[i]，即p[i]在S中的位置.

我們只需枚舉 1至length(p) 并判斷 a[i] && b[i+1] && a[i]<b[i+1]? 即可.

如果滿足這個條件，就說明這個詢問是有解的.

要注意判斷一下長度為 1 的情況，這顯然是無解的.