我们有一条长度为 N 的 DNA(由 A
、C
、G
、T
四个字母组成的一条链),定义为 S。
定义两个字符匹配当且仅当这两个字符为 A,T
或 C,G
时匹配。
你需要找到 S 中非空子串 T 的数量,使得对于每一个 T,都有一个 T′ 是 T 的排列,并且和 T 一一配对。
对于不同位置上的 T,即便内容相同,也计两次。
两个 T 为 GC
和 ACGT
。
四个 T 分别 AT
(两个)、TA
和 ATAT
。
对于 100% 的数据,1≤N≤5000,S 中只含有 A
、C
、G
、T
。