4169: DNA序列---复制问题

    核酸与蛋白质是生物体内两大重要的生物大分子，其中核酸是生物遗传信息从上一代传到下一代的的重要载体。核酸的基本组成单元是核苷酸，可将核苷酸分为脱氧核苷酸(DNA)和核糖核苷酸(RNA)。 
    我们以DNA为例，所有的DNA核苷酸的磷酸基团和糖基团都是一样的，但其化学组成的碱基基团有四种类型，腺嘌呤（A）、鸟嘌呤（G）、胞嘧啶（C）、胸腺嘧啶（T）。因此，对DNA序列的单链研究可以转化为研究由A、G、C、T四个字母组成的字符串。 
    DNA复制是指以原始的DNA分子为模板合成出相同分子的过程。在一些酶的作用下，DNA复制过程的有四种可能：完全复制、半保留复制、逆复制、逆半保留复制。 
    给定一个带有遗传信息的模板mode，你能在DNA序列s中找到这样的复制过程最多有多少次？

第一行：整数T ， 表示以下有T组测试数据             （ 1 ≤ T ≤ 4） 
每组数据， 占一行： 
mode  s （|mode |≤ 20，    |s| ≤ 1000 ， mode与s之间只有一个空格） 

对每组测试数据，输出占一行。

2
ACGA AGACGACGAGCAGCAACGA
AAA ACGATTAAAAAGTCTAAAA 

5
5

1 半保留复制是指本次复制可以与前次复制部分重叠。例如：ACGACGA,算2次复制。类似逆半保留 
复制，例如：AGCAGCA,算2次复制。 
2 若模板是回文串，逆复制过程不再统计。