1147. 段式回文

题目描述：

你会得到一个字符串 text 。你应该把它分成 k 个子字符串 (subtext1, subtext2，…， subtextk) ，要求满足:

subtexti 是 非空 字符串
所有子字符串的连接等于 text ( 即subtext1 + subtext2 + … + subtextk == text )
对于所有 i 的有效值( 即 1 <= i <= k ) ，subtexti == subtextk - i + 1 均成立
返回k可能最大值。

示例 1：

输入：text = “ghiabcdefhelloadamhelloabcdefghi”
输出：7
解释：我们可以把字符串拆分成 “(ghi)(abcdef)(hello)(adam)(hello)(abcdef)(ghi)”。
示例 2：

输入：text = “merchant”
输出：1
解释：我们可以把字符串拆分成 “(merchant)”。
示例 3：

输入：text = “antaprezatepzapreanta”
输出：11
解释：我们可以把字符串拆分成 “(a)(nt)(a)(pre)(za)(tpe)(za)(pre)(a)(nt)(a)”。

提示：

1 <= text.length <= 1000
text 仅由小写英文字符组成

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/longest-chunked-palindrome-decomposition
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：
虽然标注的是困难级别的，但其实并没有困难的难度。

本题和正常分割回文串的不同之处在于，这里的单元可以不是一个字母而是一个词。

那其实思路还是很好想的。用双指针的思想，从前和从后两个方向进行移动和判断，当前面的词等于后面的词的时候，那说明当前长度是可以分割的，而且是前面分割一次，后面分割一次，这样就会使得 res += 2 。

如果当前分割之后，中间剩余部分不能再分割，res++ ； 如果还可以继续分割，就继续重复上述的步骤，然后最后判断res是否需要+1 。

值得注意的是，因为题目问的是最多可以分割多少块，所以我们上述思路中的策略是，前后指针发现前后两个部分是相等的时候，就直接分割，这样类似贪心的思想可以得到最大的解。

那大体思路结束了，再写一个判断两个字符串是否相等，代码就完成了。

代码：

class Solution {
public:bool check(string text , int l1 , int l2 , int len){while(len--){if(text[l1] != text[l2]){return false;}l1++;l2++;}return true;}int longestDecomposition(string text) {int n = text.size();int res = 0;int l = 0;int r = n-1;while(l <= r){int len = 1;while(l+len-1 < r-len+1){if(check(text , l , r-len+1 , len)){res += 2;break;}len++;}if(l+len-1 >= r-len+1){res++;}l += len;r -= len;}return res;}
};