链接：

​​​​​​1147. 段式回文

题解：

class Solution {
public:int longestDecomposition(string text) {MOD = 1e9 + 7;if (text.size() <= 0) {return 0;}// 初始化26的n次方的表pow26.resize(text.size());pow26[0] = 1;for (int i = 1; i < text.size(); ++i) {pow26[i] = (pow26[i-1] * 26 ) % MOD;}return calc(text, 0, text.size()-1);}
private:int calc(const std::string& text, int left, int right) {if (left > right) {return 0;}//[left, i] 和[j, right] 判断是否相等// 贪心：如果字符串可以构成段式回文，则继续向下一层判断[i+1, j-1]long prefix_hash = 0;long post_hash = 0;// i < j 两个区间不能有交集for (int i = left, j = right; i < j; ++i, --j) {// 求的前后缀的hash数值prefix_hash = (prefix_hash * 26 + (text[i] - 'a'))%MOD;post_hash = ((text[j]-'a')*pow26[right-j] + post_hash)%MOD;if (prefix_hash == post_hash && equal(text, left, i, j, right)) {return 2 + calc(text, i+1, j-1);}}// 如果拆分不出来就是1段return 1;}bool equal(const std::string& text, int i, int left, int j, int right) {// 判断两个子串是否相等for (; i <= left && j <= right; ++i, ++j) {if (text[i] != text[j]) {return false;}}return true;}
private:long MOD;std::vector<long> pow26;
};