302343: CF451D. Count Good Substrings

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Count Good Substrings

题意翻译

### 题目描述 一个字符串是“好的”,当且仅当合并其中的连续区间后,它是一个回文串。比如“`aabba`”是好的,因为在合并后它变成了`aba` 给你一个字符串,现在要你分别求出长度为奇数和偶数的“好的”子串数量。(提示:不是本质不同的子串,不允许空串) ### 输入格式 一行,字符串$s$ ### 输出格式 一行,两个空格隔开的整数,分别为长度是偶数和奇数的“好的”字串数量。 ### 样例解释 样例1中,有$s[1..1]= ``b"$,$s[2..2] = ``b"$和$s[1..2]= ``bb"$是好的。 样例2中,好的子串有:"$b$", "$a$", "$a$", "$b$", "$aa$", "$baab$" 样例3中,好的子串有:"$b$", "$a$", "$b$", "$b$", "$bb$", "$bab$", "$babb$" ### 数据范围 $1 \leq |s| \leq 10^5$,其中$|s|$是字符串的长度。 字符串只包含小写$a$和$b$两种字符。

题目描述

We call a string good, if after merging all the consecutive equal characters, the resulting string is palindrome. For example, "aabba" is good, because after the merging step it will become "aba". Given a string, you have to find two values: 1. the number of good substrings of even length; 2. the number of good substrings of odd length.

输入输出格式

输入格式


The first line of the input contains a single string of length $ n $ ( $ 1<=n<=10^{5} $ ). Each character of the string will be either 'a' or 'b'.

输出格式


Print two space-separated integers: the number of good substrings of even length and the number of good substrings of odd length.

输入输出样例

输入样例 #1

bb

输出样例 #1

1 2

输入样例 #2

baab

输出样例 #2

2 4

输入样例 #3

babb

输出样例 #3

2 5

输入样例 #4

babaa

输出样例 #4

2 7

说明

In example 1, there are three good substrings ("b", "b", and "bb"). One of them has even length and two of them have odd length. In example 2, there are six good substrings (i.e. "b", "a", "a", "b", "aa", "baab"). Two of them have even length and four of them have odd length. In example 3, there are seven good substrings (i.e. "b", "a", "b", "b", "bb", "bab", "babb"). Two of them have even length and five of them have odd length. Definitions A substring $ s[l,r] $ $ (1<=l<=r<=n) $ of string $ s=s_{1}s_{2}...\ s_{n} $ is string $ s_{l}s_{l+1}...\ s_{r} $ . A string $ s=s_{1}s_{2}...\ s_{n} $ is a palindrome if it is equal to string $ s_{n}s_{n-1}...\ s_{1} $ .

Input

题意翻译

### 题目描述 一个字符串是“好的”,当且仅当合并其中的连续区间后,它是一个回文串。比如“`aabba`”是好的,因为在合并后它变成了`aba` 给你一个字符串,现在要你分别求出长度为奇数和偶数的“好的”子串数量。(提示:不是本质不同的子串,不允许空串) ### 输入格式 一行,字符串$s$ ### 输出格式 一行,两个空格隔开的整数,分别为长度是偶数和奇数的“好的”字串数量。 ### 样例解释 样例1中,有$s[1..1]= ``b"$,$s[2..2] = ``b"$和$s[1..2]= ``bb"$是好的。 样例2中,好的子串有:"$b$", "$a$", "$a$", "$b$", "$aa$", "$baab$" 样例3中,好的子串有:"$b$", "$a$", "$b$", "$b$", "$bb$", "$bab$", "$babb$" ### 数据范围 $1 \leq |s| \leq 10^5$,其中$|s|$是字符串的长度。 字符串只包含小写$a$和$b$两种字符。

加入题单

上一题 下一题 算法标签: