https://codeforces.com/contest/1037/problem/H

題意：

給出一個(gè)文本串 S? ?，有 Q? ?次詢問，每次詢問給出模式串 T，

問在 S? 串中 [ l , r ]? 區(qū)間上是否存在比 T? ?的字典序大的子串，

如果存在輸出其中字典序最小的那個(gè)子串，否則輸出 ? 1?

?

題解：

后綴自動(dòng)機(jī) + 線段樹??

后綴自動(dòng)機(jī)中每個(gè)字符串節(jié)點(diǎn)出現(xiàn)位置上傳到線段樹，

一個(gè)字符串可能出現(xiàn)多次，因而在線段樹上也有多個(gè)位置。

與模式串 T匹配時(shí)，同時(shí)使用后綴自動(dòng)機(jī) + 線段樹，非常經(jīng)典的技術(shù)。

使用后綴自動(dòng)機(jī)可以知道模式串 T是否存在，使用線段樹可以知道模式串 T的出現(xiàn)位置。