e148: PL. Least Suffix(最小後綴)
Tags :
Accepted rate : 7人/11人 ( 64% ) [非即時]
評分方式:
Tolerant

最近更新 : 2019-07-03 22:54

Content

給一個長度為$n$的字串$s = s_1 s_2 s_3...s_n$。$s$會有$n$個後綴,第$i$個後綴為 suffix($s$,$i$) $= s_i s_{i+1}...s_n$,請輸出字典序最小的後綴是$s$的第幾個後綴?

字串$A$的字典順序小於字串$B$的字典順序,若且唯若$B$是$A$的前綴,或者存在一個正整數$k$,滿足

  • $k \leq \lvert A\rvert, k \leq \lvert B\rvert$
  • $A_k \lt B_k$ (ASCII code)
  • $A_i = B_i, \forall 1 \leq i \lt k$

 

Input

第1⾏有⼀個正整數$T(1 \leq T \leq 100000)$, 表⽰有$T$ 筆測試資料
對於每筆測試資料佔⼀⾏,只包含⼀個由⼤⼩寫英⽂字⺟及數字(62 種字元) 所組成的字串
保證輸⼊資料⼩於5MB

Output

對於每筆測試資料,依照輸⼊的順序,個別輸出⼀個數字,為這個字串的最⼩字典序後綴後綴的編號。

 

Sample Input
4
banana
anana
ana
a
Sample Output
2
1
1
1
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (25%): 0.2s , <1K
公開 測資點#1 (25%): 0.2s , <10M
公開 測資點#2 (25%): 0.2s , <10M
公開 測資點#3 (25%): 0.2s , <10M
Hint :
Tags:
出處:
2019 NCTU PCCA Winter [管理者:
qqrainbow (愛蜜莉雅 準•指考戰士)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」