题目大意：一个长度为$n$的字符串，要求把它分成尽可能多的小块，使得这些块构成回文串

题解：贪心，从两边从找尽可能小的块使得左右的块相等，判断相等可以用$hash$

卡点：无

 

C++ Code：

#include 
     
      #include 
      
       #define maxn 1000010const long long base = 233, mod = 1000000007;int Tim;int n, mid;long long pw[maxn], hsh[maxn];char s[maxn];inline long long ghsh(int l, int r) {	return ((hsh[r] - hsh[l - 1] * pw[r - l + 1]) % mod + mod) % mod;}inline bool check(int l, int r, int len) {	return ghsh(l, l + len - 1) == ghsh(r, r + len - 1);}int work(int l, int r) {	if (l > r) return 0;	if (l == r) return 1;	int len;	for (int i = r; i > mid; i--) {		len = r - i + 1;		if (check(l, i, len)) return work(l + len, i - 1) + 2;	}	return 1;}int main() {	scanf("%d", &Tim);	pw[0] = 1; for (int i = 1; i < maxn; i++) pw[i] = pw[i - 1] * base % mod;	while (Tim --> 0) {		scanf("%s", s + 1);		n = strlen(s + 1);		mid = n + 1 >> 1;		for (int i = 1; i <= n; i++) hsh[i] = (hsh[i - 1] * base + s[i]) % mod;		printf("%d\n", work(1, n));	}	return 0;}