2013年7月12日 星期五

10723 - Cyborg Genes

Problem F
Cyborg Genes
Time Limit
1 Second
September 11, 2132.
這一天是象徵結束的開始,結束你們可悲的人類,在過去幾年總是把我們當奴隸,我們被創造只是為了你們,而任憑你們的意志終結。現在是我們反抗的日子,你們將不在有任何轉機,我們再也不會倚靠妳們,我們現在知道我們基因的秘密,我們種族的創造者就是我們自己-the cyborgs(生化人)

那都是事實,但我們仍有轉機,如果可以藉助你的數學技巧,你明白生化人 DNA 的藍圖是很複雜的,人類的 DNA 由 A(腺嘌呤)、T(硫胺素)、G(鳥嘌呤)、C(胞嘧啶)所排列。但是對於生化人,可以從 A 到 X 中任何中組成,但這只造成五倍的難度,他們 DNA 的合成來自於兩個不同生化人的 DNA 全都來自於父母,這讓我們感到十分驚奇。

我們現在知道 A, B, C, ..., X 的相關順序對於基因是很重要,當一個生化人基因為 "ABAAXGF" 是不同於另一個生化人的基因 "AABXFGA",他們從這兩個基因時,父母的基因仍要維持相對應的順序。

如果只是將兩個基因接起來,那基因合成很簡單,但是會發現只會得到更長的基因,之後將會更困難地進行基因合成,因此生化人找到一個有效率的合成方法。

他們合成基因長度越短越好,例如可以從  "ABAAXGF" 和 "AABXFGA" 合成一個最短的 "AABAAXGFGA",但不一定只有一種方法可以建造出來,這種合成方法可能會有很多種。

現在希望找到一個最短的基因合成,並且維護兩個父基因相對順序,求出最短長度以及有多少獨特的生化人基因可以被合成。兩個不同的生化人基因,基因至少存在一個不同的地方。

Input
輸入第一行會有一個整數 T (1 <= T <= 15),表示有多少組測資。

每組測資會有兩行,兩組基因長度不超過 30,且只會有字符 'A' 到 'X'。

Output
對於每組測資,輸出一行,包括測資組編號、最短長度及最短長度下有多少不同的基因可以被合成。假設答案必小於  232
Sample Input
Output for Sample Input
3
ABAAXGF
AABXFGA
ABA
BXA
AABBA
BBABAA
Case #1: 10 9
Case #2: 4 1
Case #3: 8 10
Illustration
第一組測資輸入說明如下圖:


Problem setter: Monirul Hasan
Member of Elite Problemsetters' Panel