e148. PL. Least Suffix(最小後綴) - 高中生程式解題系統

內容

給一個長度為 $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 | A |, k \leq | B |$
$A_{k} < B_{k}$ (ASCII code)
$A_{i} = B_{i}, \forall 1 \leq i < k$

輸入說明

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

輸出說明

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

範例輸入 #1

4
banana
anana
ana
a

範例輸出 #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 [管理者： emiliaistruelove@gmail.com

qqrainbow (愛蜜莉雅) ]

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