题目地址：Codeforces：Problem – 7D – Codeforces、洛谷：CF7D Palindrome Degree – 洛谷 | 计算机科学教育新生态

题目描述

String s of length n is called k-palindrome, if it is a palindrome itself, and its prefix and suffix of length $\lfloor n/2 \rfloor$ are (k - 1)-palindromes. By definition, any string (even empty) is 0-palindrome.

Let’s call the palindrome degree of string s such a maximum number k, for which s is k-palindrome. For example, “abaaba” has degree equals to 3.

You are given a string. Your task is to find the sum of the palindrome degrees of all its prefixes.

题意简述

定义长度为$n$的字符串$s$为一个$k$阶回文串，当且仅当它本身是一个回文串，且它的长度为$\lfloor n/2 \rfloor$的前缀和后缀（即前半部分和后半部分）都是$(k-1)$阶的回文串。根据定义，任何一个字符串（包括空串）都至少是一个$0$阶回文串。

给定一个字符串，求它所有前缀的回文串阶数之和。

输入输出格式

输入格式：
The first line of the input data contains a non-empty string, consisting of Latin letters and digits. The length of the string does not exceed 5·10⁶. The string is case-sensitive.

输出格式：
Output the only number — the sum of the polindrome degrees of all the string’s prefixes.

输入输出样例

输入样例#1：

a2A

输出样例#1：

1

输入样例#2：

abacaba

输出样例#2：

6

题解

题目已经说明了这个题的基本思路，即判断当前前缀是否是一个回文串，若是一个回文串则完成转移$f(i)=f(i/2)+1$，其中$f(i)$是前缀$s_{1 \dots i}$的回文串阶数，且$f(1)=1$。

判断是否相等可以通过字符串Hash来实现，这里不再赘述字符串Hash的原理。

复杂度$O(n)$。

代码

// Code by KSkun, 2019/8
#include <cstdio>
#include <cstring>

#include <algorithm>

typedef long long LL;

const int MAXN = 5000005;
const int BASE = 233, MO = 998244353;

int n, f[MAXN];
LL h1[MAXN], h2[MAXN], bpow[MAXN];
char s1[MAXN], s2[MAXN];

inline LL fpow(LL n, LL k) {
	n %= MO; LL res = 1;
	for(; k; k >>= 1, n = n * n % MO) {
		if(k & 1) res = res * n % MO;
	}
	return res;
}

inline LL hash(LL hsh[], int l, int r) {
	return (hsh[r] - hsh[l - 1] * bpow[r - l + 1] % MO + MO) % MO;
}

int main() {
	scanf("%s", s1 + 1);
	n = strlen(s1 + 1);
	for(int i = 1; i <= n; i++) s2[n - i + 1] = s1[i];
	bpow[0] = 1;
	for(int i = 1; i <= n; i++) bpow[i] = bpow[i - 1] * BASE % MO;
	for(int i = 1; i <= n; i++) h1[i] = (h1[i - 1] * BASE % MO + s1[i]) % MO;
	for(int i = 1; i <= n; i++) h2[i] = (h2[i - 1] * BASE % MO + s2[i]) % MO;
	f[1] = 1; int sum = 1;
	for(int i = 2; i <= n; i++) {
		if(hash(h1, 1, i / 2) == hash(h2, n - i + 1, n - i + i / 2)) f[i] = f[i / 2] + 1;
		sum += f[i];
	}
	printf("%d", sum);
	return 0;
}