分数: 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