← 返回题目列表

Codeforces · 451/D

D. 计算好子串

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

如果将所有连续的相等字符合并后,得到的字符串是回文,我们称一个字符串为好字符串。例如,“aabba”很好,因为在合并步骤之后它将变成“aba”。

给定一个字符串,您必须找到两个值:

1. 偶数长度的好子串的数量;
2.奇数长度的好子串的数量。

输入

输入的第一行包含长度为 n (1 ≤ n ≤ 105) 的单个字符串。字符串的每个字符都是“a”或“b”。

输出

打印两个空格分隔的整数:偶数长度的好子串的数量和奇数长度的好子串的数量。

示例

输入 #1

bb

输出 #1

1 2

输入 #2

baab

输出 #2

2 4

输入 #3

babb

输出 #3

2 5

输入#4

babaa

输出#4

2 7

注意

在示例 1 中,存在三个好的子字符串(“b”、“b”和“bb”)。其中一个长度为偶数,两个长度为奇数。

在示例 2 中,有 6 个好的子字符串(即“b”、“a”、“a”、“b”、“aa”、“baab”)。其中两个长度为偶数,四个长度为奇数。

在示例 3 中,有七个好的子字符串(即“b”、“a”、“b”、“b”、“bb”、“bab”、“babb”)。其中两个长度为偶数,五个长度为奇数。

定义

字符串 s = s1s2... sn 的子字符串 s[l, r] (1 ≤ l ≤ r ≤ n) 是字符串 slsl + 1... sr。

如果字符串 s = s1s2... sn 等于字符串 snsn - 1... s1,则它是回文。