回分類題庫
h215: D.回文樹
關鍵字: NPSC 2019 高中組決賽

測資點 : 9 | Time Limit : 2000 ms | Memory Limit : 128000 KB
Accepted : 10 Times / 8 Users | Submit : 61 Times / 14 Users | Accepted rate : 57%
題目加入時間 : 2020-11-13 23:53

Content: 简体中文

你聽過回文樹嗎?這是⼀種可以在 O(N|Σ|) 的時間內算出一個長度為 N 的字串 S 的所有回文子字串出現次數的資料結構,其中 |Σ| 為字元集的大小。例如,當 S 是 abacaba 時,子字串 a 、b 、aba 、aca 、bacab 、abacaba 皆是回文,且其中 aba 出現了兩次、a 出現了四次。

由於回文樹不僅功能強大,種在路邊作為行道樹也可以美化市容。更重要的是,如果用回文來灌溉它的話,它就會將城市中的廢氣轉為清新的空氣!長年受到空氣污染影響的 NPSC 國當然不會放過這個機會,因此 NPSC 國政府從回文樹的原⽣地 CSPN 國購進了大量的回文樹,並打算用大量的回文來灌溉它。

不過,NPSC 國很快就發現了,如果灌溉用的回文的字典序不夠小的話,可能反而造成反效果,使得回文樹枯萎而死。因此,政府打算重新排列手上的字串,使得它變成回文且字典序最小。請幫助 NPSC 國找到字典序最小的回文,解決空汙的問題! 

Input:

輸入第一行有一個正整數 T ,代表回文樹的肥料個數。接著 T 行,每行有⼀個非空字串 S,代表⼀個灌溉用的字串。

Output:

輸出 T 行,每行代表該字串重新排列後能夠造成的最小回文。若不存在⼀種重排成回文的方式,輸出 NPSCCSPN 。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
2
ACCBBA
ABC

Sample Output :

ABCCBA
NPSCCSPN

Hint :

Author :

NPSC 2019 高中組決賽 (管理員:sagit)

  Solve it!   Status Forum