TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

100.0% (49/49)

Submission's AC Ratio

83.5% (66/79)

Tags

Description

許多壓縮法則並不會直接壓縮輸入的訊息,他們通常在執行壓縮前會對輸入的訊息做一些前置處理,能讓此訊息有效率地壓縮。以下說明一種前置處理的方式,稱之為Burrows-Wheeler (BW)轉換。

假設輸入一個字串S,其包含的字母個數為N,則BW 轉換的第一個步驟便是依據下列的兩個式子另外產生N個新字串,分別為S1, S2,...,SN

  1. 字串S1等於S。

  2. 字串Sk向左位移一個字母,第一個字母放到最後一個位置,即可得字串Sk+1,其中1<=k<N。

以下為BW 轉換的第一個步驟之實例,假設輸入一個字串S="WHEELER",其中字母個數N = 7,則產生的新字串如下所示:

在BW 轉換之第二個步驟中我們將這N個新字串排序。首先依據每個字串之第一個字母(從最左邊算起)排序,字母在排序時的大小順序為A > B > C > … > Z。若有某些字串第一個字母相同,則這些字串間的排序依照第二個字母。若仍相同,則依照第三個字母,依此類推到第N個字母為止。承續第一步驟的實例,其排序結果如下所示:

其中S3,S4,S6字串中的第一個字母皆相同,因此這三個字串的排序順序由第二個字母比較而得。
在BW 轉換完成後,我們需要的結果為兩個:

  1. 排序後第N欄形成的字串;即為依序抓出每列的最後一個字母形成需要的字串,所以在本例中最後一欄形成的字串為"HELWEER";

  2. S2所在的列位置;在本例中為4 (列數從1 開始計算,非從0 開始)。

本題即是請你撰寫上述Burrows-Wheeler 轉換的程式。

Constraints

輸入字串及產生的新字串中僅限於大寫的英文字母,輸入的字串中至少有兩個相異字母。

Input Format

輸入檔可能包含多筆測試資料。
每筆測試資料佔兩行,第一行為字串的字母個數N,2<=N<=20;第二行為字串S。

Output Format

對於每筆測試資料輸出兩行,第一行為第二步驟後的第N欄字母,第二行為第二步驟後S2 所在的列位置。注意列數從1 開始計算,非從0 開始。

Sample Input 1

7
WHEELER
6
MYTEST
5
NANNY

Sample Output 1

HELWEER
4
TTEYSM
6
NYANN
1

Hints

Problem Source

原TIOJ1121 / 93北市賽(prob 2)

Subtasks

No. Testdata Range Score
1 0 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1