碱基对是由两个互相通过氢键结合的核碱基组成的双链核酸的基本单位。 这些化学键将两条脱氧核糖核酸（DNA）链粘合在一起。 它们构成了DNA双螺旋的基本组成部分，并影响DNA和RNA的折叠结构。 DNA中有四种核苷酸：腺嘌呤（A）、胞嘧啶（C）、鸟嘌呤（G）和胸腺嘧啶（T）。 核苷酸是由脱氧核糖，含氮碱基及磷酸基团制成，在DNA中以磷酸二酯键结合在一起。 "Watson-Crick"碱基对（A-T 和 C-G）使得DNA螺旋保持规则的螺旋结构，这种结构的稳定性依赖于其核苷酸序列。
你是一位生物信息学家。 现在有两个单链DNA（ssDNA）链，$S$ 和 $T$，你希望将DNA进行配对，并形成稳定的氢键。 例如，ATTCG和TAAGC之间能形成稳定的氢键，但ATTCG和TAACC则不能。 作为一位很无聊的生物信息学家，你想要找到可形成稳定氢键的连续DNA片段的数量。
输入
输入的第一行包含一个字符串$S$。
输入的第二行包含一个字符串$T$。
输出
输出能形成稳定氢键的连续DNA片段的数量。
数据范围
对于所有测试点，$1 \le |S|, |T| \le 10^6$，且 $S_i,T_i \in \{$'A', 'T', 'C', 'G'$\}$。
| Case | $\max(|S|, |T|)$ |
|---|---|
| 1-3 | $\le 50$ |
| 4-8 | $\le 500$ |
| 9-15 | $\le 1000$ |
| 16-22 | $\le 10^5$ |
| 23-25 | $\le 10^6$ |
Sample Test Cases
| Input | Output | |
|---|---|---|
| ACCAG ATGGCA |
6 | |
| 在$S$中的"G"可以与在$T$中的"C"作匹配。 同样地"C"可以与"G"作匹配。 "CC"可以与"GG"作匹配。 "A"可以与"T"作匹配。 "AC"可以与"TG"作匹配。 "ACC"可以与"TGG"作匹配。 |
||
| TAGC ATGATCG |
10 | |
| AAAAAA AAAAAAAAAAAAAAAAAATA |
1 | |
| ATTCGACG CCTAAGC |
15 | |
| "T"可以与"A"作匹配。 "TT"可以与"AA"作匹配。 "TTC"可以与"AAG"作匹配。 "TTCG"可以与"AAGC"作匹配。 "TC"可以与"AG"作匹配。 "TCG"可以与"AGC"作匹配。 "G"可以与"C"作匹配。 "GA"可以与"CT"作匹配。 "C"可以与"G"作匹配。 "CG"可以与"GC"作匹配。 "A"可以与"T"作匹配。 "AT"可以与"TA"作匹配。 "ATT"可以与"TAA"作匹配。 "ATTC"可以与"TAAG"作匹配。 "ATTCG"可以与"TAAGC"作匹配。 |
||
Scoring: Per Case
Authored by s17r38
Appeared in 2023 Mini Contest 7 （sdic练习）