← 返回题目列表

AtCoder · arc104_b

B. DNA 序列

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

我们有一个字符串 S 长度 N 组成 A, T, C,和 G.

字符串 当对于每个相同长度的 T_1 和 T_2 被认为是互补的 i (1 \leq i \leq l), i- 第一个字符 T_1 和 i- 第一个字符 T_2 是互补的。在这里, A 和 T 是互补的,因此 C 和 G.

查找非空连续子串的数量 T of S 满足以下条件:

  • 存在一个字符串,它是以下的排列 T 并且是互补的 T.

在这里,我们区分源自不同位置的字符串 S,即使内容相同。

约束

  • 1 \leq N \leq 5000
  • S 包括 A, T, C,和 G.

输入

输入由标准输入按以下格式给出:

N S

输出

打印非空连续子串的数量 T of S 满足条件。


示例输入 1

4 AGCT

示例输出 1

2

以下两个子字符串满足条件:

  • GC ( 2-nd 通过 3-rd 字符)是互补的 CG,这是一个排列 GC.
  • AGCT ( 1-st 通过 4-th 个字符)与 TCGA,这是一个排列 AGCT.

示例输入 2

4 ATAT

示例输出 2

4

以下四个子字符串满足条件:

  • AT ( 1-st 通过 2-nd 字符)是互补的 TA,这是一个排列 AT.
  • TA ( 2-st 通过 3-rd 字符)是互补的 AT,这是一个排列 TA.
  • AT ( 3-rd 通过 4-th 个字符)与 TA,这是一个排列 AT.
  • ATAT ( 1-st 通过 4-th 个字符)与 TATA,这是一个排列 ATAT.

示例输入 3

10 AAATACCGCG

示例输出 3

6