题目描述

段式回文 其实与 一般回文 类似，只不过是最小的单位是 一段字符 而不是 单个字母。

举个例子，对于一般回文 "abcba" 是回文，而 "volvo" 不是，但如果我们把 "volvo" 分为 "vo"、"l"、"vo" 三段，则可以认为 "(vo)(l)(vo)" 是段式回文（分为 3 段）。

给你一个字符串 text，在确保它满足段式回文的前提下，请你返回 段 的 最大数量 k。

如果段的最大数量为 k，那么存在满足以下条件的 a_1, a_2, ..., a_k：

• 每个 a_i 都是一个非空字符串；
• 将这些字符串首位相连的结果 a_1 + a_2 + ... + a_k 和原始字符串 text 相同；
• 对于所有 1 <= i <= k，都有 a_i = a_{k+1 - i}。

样例

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

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

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

输入：text = "aaa"
输出：3
解释：我们可以把字符串拆分成 "(a)(a)(a)"。

限制

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

算法

(贪心) $O(n^2)$

1. 可以证明，如果能找到最短的字符串的前缀和后缀，则我们就将其拆分出来。这样迭代下去，一定是答案最大的。
2. 也就是说，不存在一个因为拆分出了长度更小的段，而导致整体答案变小的情况。
3. 所以我们可以通过枚举首尾的情况，来拆分字符串。
4. 对于当前字符串，从小到大枚举长度 len 表示期望的相同的段的长度，直到当前字符串长度的一半，然后枚举判断前缀和后缀子串是否相同。
5. 如果找到了一个相同的前后缀，则答案加 2，更新字符串重新迭代；否则答案加 1，退出迭代。

时间复杂度

• 最坏情况下，整个字符串不可拆分，此时需要 $O(n^2)$ 的时间去枚举验证。
• 故时间复杂度为 $O(n^2)$。

空间复杂度

• 没有用任何额外的数组，故空间复杂度为 $O(1)$。

C++ 代码

class Solution {
public:
    bool check(int l, int r, int len, const string& text) {
        for (int i = l, j = r - len + 1; j <= r; i++, j++)
            if (text[i] != text[j])
                return false;

        return true;
    }

    int longestDecomposition(string text) {
        int n = text.length();
        int l = 0, r = n - 1;
        int ans = 0;
        while (l <= r) {
            int length = r - l + 1;
            bool flag = false;
            for (int len = 1; len <= length / 2; len++)
                if (check(l, r, len, text)) {
                    l += len;
                    r -= len;
                    flag = true;
                    break;
                }

            if (!flag) {
                ans++;
                break;
            }
            else
                ans += 2;
        }
        return ans;
    }
};