【CF 1051E】Vasya and Big Integers

原題連結：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(n) \space}$

附上code: