首页 > ACM题库 > HDU-杭电 > hdu 4482 Base pairing待解决[解题报告]C++
2015
07-16

hdu 4482 Base pairing待解决[解题报告]C++

Base pairing

问题描述 :

  We have two straight parallel DNA single strands. You can shift any strand left or right, but you can not reverse it or bent it.
  Your task is to calculate how many paired bases at most between the two strands. Note that the paired bases can only be A-T, T-A, C-G or G-C.

输入:

  There is an integer T (1 <= T <= 100) in the first line, indicates there are T test cases in total.
  For each test case, there are two lines, and each line contains one DNA single strand. You can assume that there are only “A”, “T”, “C” or “G” in the two strands. The length of each strand is at least 1 and not more than 30000.
  There are at most 10 test cases that satisfy the total length of the two strands is more than 200.

输出:

  There is an integer T (1 <= T <= 100) in the first line, indicates there are T test cases in total.
  For each test case, there are two lines, and each line contains one DNA single strand. You can assume that there are only “A”, “T”, “C” or “G” in the two strands. The length of each strand is at least 1 and not more than 30000.
  There are at most 10 test cases that satisfy the total length of the two strands is more than 200.

样例输入:

3
ATC
GAT
ATCG
TGC
CTAG
TGAT

样例输出:

1
2
3
Hint
Slalom