許多壓縮法則並不會直接壓縮輸入的訊息,他們通常在執行壓縮前會對輸入的訊息做一些前置處理,能讓此訊息有效率地壓縮。以下說明一種前置處理的方式,稱之為Burrows-Wheeler (BW)轉換。
假設輸入一個字串S,其包含的字母個數為N,則BW 轉換的第一個步驟便是依據下列的兩個式子另外產生N個新字串,分別為S1, S2,...,SN。
本題即是請你撰寫上述Burrows-Wheeler 轉換的程式。
Constraints 輸入字串及產生的新字串中僅限於大寫的英文字母,輸入的字串中至少有兩個相異字母。
輸入檔可能包含多筆測試資料。
每筆測試資料佔兩行,第一行為字串的字母個數N,2<=N<=20;第二行為字串S。
對於每筆測試資料輸出兩行,第一行為第二步驟後的第N欄字母,第二行為第二步驟後S2 所在的列位置。注意列數從1 開始計算,非從0 開始。
原TIOJ1121 / 93北市賽(prob 2)
No. | Testdata Range | Score |
---|---|---|
1 | 0 | 100 |