隨手coding筆記 by波路特石

原題連結： http://codeforces.com/problemset/problem/1051/E 這題大概瞪個一眼就會發現是DP了 但是問題在轉移，怎麼想都很容易TLE 總之如果列出轉移式的話，大概會長這樣 $\color{white}{\space dp[i]=\displaystyle\sum_{l\leq substring (j,i]\leq r} dp[j] \space}$ 那就是要想辦法搜到滿足的$\color{white}{\space j \space}$的範圍，可以發現存在單調性，衝動之下可能就會想二分搜了 可以用hash來達成類似的動作，複雜度約為$\color{white}{\space O(nlogn) \space}$ 但是hash容易被攻擊，$\color{white}{\space O(nlogn) \space}$又感覺怕怕的 有沒有一個優美又是$\color{white}{\space O(n) \space}$的解呢？ 有！ 觀察字串比大小時的動作，也就是找到兩個字串的$\color{white}{\space LCP \space}$再比較下一個字元的大小 仔細看了一下，找$\color{white}{\space LCP \space}$的動作都是發生在字串$\color{white}{\space l,r \space}$跟字串$\color{white}{\space a \space}$的每個元素開始比較 那如果能預處理這些東西的$\color{white}{\space LCP \space}$，不就能$\color{white}{\space O(1) \space}$定位了嗎？ 當然這裡絕對不會把Suffix Array搬出來 Z-value就足夠了！ 把字串$\color{white}{\space a \space}$分別接在$\color{white}{\space l,r \space}$後面求Z-value，就完成預處理$\color{white}{\space LCP \space}$了 那區間的DP值也只不過是做點前綴處理而已(要記得判掉前綴0，跟反處理掉單一個0的情況) 整體就完全是線性的$\color{white}{\space O(...