將輸入的原字串$s[1\dots n]$和自身做concatenation 得到$t[1\dots 2n]=s[1]s[2]\dots s[n]s[1]s[2]\dots s[n]$
我們要找一個$1\le i\le n$使得$t[i\dots 2n]$是$t[1\dots 2n],t[2\dots 2n],\dots ,t[n\dots 2n]$中字典序第$K$小的
這可以透過對$t$做suffix array (SA)得到
只要在$O(n)$時間建立好SA 這題應該都能在$5$秒內跑完
我的SAIS演算法跑了$1.3$秒 初音島IIIDC3演算法跑了$3.9$秒

使用doubling建立SA 時間複雜度是$O(n\log n)$ 經過測試確定在ZJ上無法在$30$秒內跑完
另外 雖然我沒有測試suffix tree的建立時間 因為它的時間複雜度是$O(|\mathrm{\Sigma }|n)$(其中$\mathrm{\Sigma }$為字元集) 應該也是會TLE的

由於坊間(?)要用到SA的題目 大多用$O(n\log n)$的演算法便綽綽有餘 決定放這題上來
如果有人有SA以外的做法也歡迎提出