CF競賽題目講解_CF700E(后綴自動(dòng)機(jī) + 線段樹 + DP)
2022-10-06 17:04 作者:Clayton_Zhou | 我要投稿
?https://codeforces.com/contest/700/problem/E
題意：
已知一個(gè)字符串S，求一個(gè)最長的字符串序列s_1,s_2,…,s_k，
所有 s_i是S的子串，且s_{i-1}在s_i里至少出現(xiàn)2次。
題解：
后綴自動(dòng)機(jī) + 線段樹 + DP
后綴自動(dòng)機(jī)中每個(gè)字符串節(jié)點(diǎn)出現(xiàn)位置上傳到線段樹，
一個(gè)字符串可能出現(xiàn)多次，因而在線段樹上也有多個(gè)位置。
在后綴自動(dòng)機(jī)樹上，由父親節(jié)點(diǎn)到子節(jié)點(diǎn)進(jìn)行DP
標(biāo)簽：
