F-信条_牛客练习赛139

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 信条-TeneT

$\hspace{15pt}$ 定义一个字符串 $t$ 是「廻文串」，当且仅当其满足以下条件之一：
$\hspace{23pt}\bullet\,$ $|t| = 1$ ，即 $t$ 是一个单字符；
$\hspace{23pt}\bullet\,$ $t$ 由非空字符串 $w$ 和其反转 $w'$ 拼接两遍构成，即 $t = ww'ww'$ ，更具体地说，记 $w$ 的长度为 $k$ ，则： $t = \underbrace{w_1 w_2 \cdots w_k}_{w} \underbrace{w_k \cdots w_2 w_1}_{w'} \underbrace{w_1 w_2 \cdots w_k}_{w} \underbrace{w_k \cdots w_2 w_1}_{w'}$ ，长度为 $4 \times k$ 。
$\hspace{15pt}$ 定义一个字符串的连续子串是「廻文子串」，当且仅当其是「廻文串」。

$\hspace{15pt}$ 现在，给定一个字符串 $s$ ，下标从 $1$ 开始，请你求解：
$\hspace{23pt}\bullet\,$ $s$ 一共有多少个「廻文子串」；
$\hspace{23pt}\bullet\,$ 最少需要多少个「廻文子串」才能够覆盖这个字符串（不要求恰好覆盖，即可以存在选中的廻文子串之间存在重叠），更具体地——对于字符串 $s$ 的 $k$ 个廻文子串 $\{s[l_i..r_i]\}_{i=1}^k$ ，若对于任意 $p \in [1, |s|]$ ，存在 $i \in [1, k]$ 使得 $l_i \leq p \leq r_i$ ，则称这 $k$ 个子串覆盖了 $s$ ；能取到的最小的 $k$ 即为答案，也可以称为最小覆盖数。

输入描述:

输入一个长度为 ，由小写字母构成的字符串 。

输出描述:

在一行上输出两个整数，分别表示  一共有多少个「廻文子串」、 的最小覆盖数。

示例1

输入

复制

abbaccabbabbbbabb

输出

复制

18 14

说明

在这个样例中， 是唯一一个长度不为  的「廻文子串」；其余  个「廻文子串」的长度均为 。
所以，最小覆盖数即为  个长度为  的「廻文子串」、  个长度为  的「廻文子串」、 个长度为  的「廻文子串」拼合而成。且在这个样例中，是恰好覆盖的。

示例2

输入

复制

aaaaa

输出

复制

7 2

说明

在这个样例中， 和  是两个不同的廻文子串，再加上  个长度为  的廻文子串（）。
有三种不同覆盖方式，均可以得到最小覆盖数 ：
；
；
。

示例3

输入

复制

aabbbbbbba

输出

复制

14 5

示例4

输入

复制

hhiihhhhhh

输出

复制

13 6