e148: PL. Least Suffix(最小後綴)
標籤 :
通過比率 : 5人/9人 ( 56% ) [非即時]
評分方式:
Tolerant

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

內容

給一個長度為$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$

 

輸入說明

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

輸出說明

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

 

範例輸入
4
banana
anana
ana
a
範例輸出
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
提示 :
標籤:
出處:
2019 NCTU PCCA Winter [管理者:
qqrainbow (愛蜜莉雅)
]


編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」