將輸入的原字串$s[1\ldots n]$和自身做concatenation 得到$t[1\ldots 2n]=s[1]s[2]\ldots s[n]s[1]s[2]\ldots s[n]$
我們要找一個$1\leq i\leq n$使得$t[i\ldots 2n]$是$t[1\ldots 2n], t[2\ldots 2n], \ldots, t[n\ldots 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(|\Sigma|n)$(其中$\Sigma$為字元集) 應該也是會TLE的

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