CF競賽題目講解_CF666E(廣義后綴自動機 + 線段樹)
2022-10-09 15:28 作者:Clayton_Zhou | 我要投稿
AC代碼
https://codeforces.com/contest/666/submission/175206059
?https://codeforces.com/contest/666/problem/E
題意：
已知一個串S，以及一個字符串數(shù)組T_{1,2,...m}，
q次詢問，每次問S的子串 S[pl，pr] 在 T_{l...r} 中的哪個串的出現(xiàn)次數(shù)最多，并輸出出現(xiàn)次數(shù)。
題解：
廣義后綴自動機+線段樹
對串 S 和數(shù)組 T 建立廣義后綴自動機。
在后綴自動機上找到S[pl，pr]這個子串對應(yīng)的節(jié)點u，?
問在 T_{l...r} 中的哪個串的出現(xiàn)次數(shù)最多，使用線段樹統(tǒng)計。
標簽：
