2022秋招备战！每天写至少一篇Leetcode里Hard难度题目的题解

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

• subtexti 是非空字符串
• 所有子字符串的连接等于 text ( 即subtext1 + subtext2 + ... + subtextk == text )
• subtexti == subtextk - i + 1 表示所有 i 的有效值( 即 1 <= i <= k )

返回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)"。

示例 4：

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

提示：

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

字符串哈希 + 双指针

题目有点长，但是题意看样例就能明白，大意就是前后同时取相等的前缀和后缀，能取则取，同时计数。

我们可以前后贪心地取相等的子串，得到的必定是最优答案，是个比较明显的结论。

比较子串的部分如果用substr会造成大量的空间和时间浪费，这里我们如果只需要比较的话则可以用字符串哈希。

p[0] = 1;
for (int i = 1; i <= n; i++) {
    p[i] = p[i - 1] * P;
    h[i] = h[i - 1] * P + text[i - 1];
}


unsigned long long query (int l, int r) {
    return h[r] - h[l - 1] * p[r - l + 1];
}

预处理好字符串哈希的hash和base数组h和p，是来自基础课的模板，text是0 based的字符串。

query可以取 1 ~ n位置之间任意子串（这个模板是从1开始的）

初始化

int l = 1, r = n, i = 1, j = n;

其中l是我们左侧的慢指针，r是右侧的慢指针，i和j分别代表左侧的快指针和右侧的快指针

我们不断移动快指针i和j，在他们不相遇的情况，如果找到2个前后字符串相等，停止移动。

把结果+2，因为我们找到了2个结果。

while(query(j, r) != query(l, i)) 
    i++, j--;
if (i <= j) k += 2;

之后我们更新i和j的值，再把慢指针和快指针统一，进行下次搜索。

i++, j--;      
l = i, r = j;

最后结果特判，如果有中间的剩余部分，比如acbac，最终我们取掉ac，还有一个b会导致结果+1

if (i != j + 1) k++;

完整代码:

class Solution {
public:
    const static int N = 1e5 + 10;
    const static int P = 131;
    unsigned long long h[N], p[N];

    unsigned long long query (int l, int r) {
        return h[r] - h[l - 1] * p[r - l + 1];
    }

    int longestDecomposition(string text) {
        int n = text.size();
        if (n == 1) return 1;
        p[0] = 1;
        for (int i = 1; i <= n; i++) {
            p[i] = p[i - 1] * P;
            h[i] = h[i - 1] * P + text[i - 1];
        }

        int k = 0;
        int l = 1, r = n, i = 1, j = n;
        while(i < j) {
            while(query(j, r) != query(l, i)) {
                i++, j--;
            }
            // 
            if (i <= j) k += 2;
            i++, j--;      
            l = i, r = j;
        }

        if (i != j + 1) k++;
        return k;
    }
};