#arc104b. [arc104_b]DNA Sequence

[arc104_b]DNA Sequence

题目翻译

我们有一条长度为 NN 的 DNA(由 ACGT 四个字母组成的一条链),定义为 SS

定义两个字符匹配当且仅当这两个字符为 A,TC,G 时匹配。

你需要找到 SS 中非空子串 TT 的数量,使得对于每一个 TT,都有一个 TT'TT 的排列,并且和 TT 一一配对。

对于不同位置上的 TT,即便内容相同,也计两次。

样例解释

样例 1 解释

两个 TTGCACGT

样例 2 解释

四个 TT 分别 AT(两个)、TAATAT

数据范围与约定

对于 100%100\% 的数据,1N50001\leq N\leq 5000SS 中只含有 ACGT