Palindromic Partitions

找一个字符串最多能切成多少块，块与块之间形成回文。这个用greedy就可以解，从两头找最短的相同的子串，找到之后重新开始这个过程，这样到最后子串的数量就是最多的。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
 
int T, n;
const int MAXN = 1000005;
char s[MAXN];
int h[MAXN], p[MAXN];
const int A = 96420, M = 1e9+7;
 
int main() {
    scanf("%d", &T);
    for (int t = 0; t < T; t++) {
        scanf("%s", s);
        n = strlen(s);
 
        p[0] = 1; h[0] = s[0];
        for (int i = 1; i < n; i++) {
            p[i] = ((ll)p[i-1] * A) % M;
            h[i] = ((ll)h[i-1] * A + s[i]) % M;
        }
        auto hsh = [](int a, int b) -> int {
            if (a == 0) return h[b];
            else return (h[b] - (ll)h[a-1] * p[b-a+1] + (ll)h[a-1] * M) % M;
        };
 
        int j = 0;
        int cnt = 0;
        for (int i = 0; i < n/2; i++) {
            if (hsh(j,i) == hsh(n-i-1,n-j-1)) {
                cnt+=2;
                j = i+1;
            }
        }
        if (j < n/2) cnt++;
        else if (j == n/2 && n%2 == 1) cnt++;       // 奇数长度剩下中间一个字符，需要处理下
 
        printf("%d\n", cnt);
    }
 
    return 0;
}