[C++]LeetCode1147. 段式回文

题目描述

Difficulty: 困难

Related Topics: 贪心, 双指针, 字符串, 动态规划, 哈希函数, 滚动哈希

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

• subtext_i是 非空字符串
• 所有子字符串的连接等于 text ( 即subtext₁ + subtext₂ + ... + subtext_k == text )
• 对于所有 i 的有效值( 即 1 <= i <= k ) ，subtext_i == subtext_{k - 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 仅由小写英文字符组成

思路

贪心 + 字符串哈希

题目要求子串不重叠，因此直接贪心即可。

从前往后扫，对每个左侧区间的左端点\(l1\)从小到大枚举区间长度\(len\)，得到区间\([l1,l1+len-1]\)，尝试与对应右侧区间\([r2-len+1,r2]\)进行匹配。能匹配上就直接划分，对新的\(l1\)枚举匹配；匹配不上就直接划成一整段。

这个过程类似双指针，根据对称性，可以直接由\(l1\)的值算出\(r2\)的值，写的时候相当于只用一个指针。

区间匹配的时候如果直接遍历，最后复杂度是\(O(n^2)\)，可以做字符串hash，将复杂度降到\(O(n)\)。

这道题数据没有构造过，直接自然溢出hash就可以了。

时间复杂度\(O(n)\)

空间复杂度\(O(n)\)（按双指针来写可以边移动指针边算hash值，做到空间复杂度\(O(1)\)）

Code

Language: C++

class Solution {
	public:
		typedef unsigned long long ull;
		static const int N = 1024;
		ull f[N] = {0}, p[N] = {0};
		int longestDecomposition(string text) {
			int n = text.size(), res = 0;
			p[0] = 1;
                        // 为了方便，将下标按[1, n]处理
			for (int i = 1; i <= n; ++i) {
				f[i] = f[i - 1] * 131 + text[i - 1] - 'a' + 1;
				p[i] = p[i - 1] * 131ull;
			}
			int l1 = 1;
			while (l1 * 2 <= n + 1) {   // 注意上界，当n为奇数时中间可能单独成段，如"abcab"
				bool check = false; // 能否匹配到右侧区间
				for (int len = 1;  (l1 + len - 1) * 2 <= n ; ++len) {
					int r1 = l1 + len - 1, r2 = n - l1 + 1, l2 = r2 - len + 1;
					if (f[r1] - f[l1 - 1] * p[len] == f[r2] - f[l2 - 1] * p[len]) {
						res += 2; // 匹配成功，左右各一段
						check = true;
						l1 = r1 + 1;
						break;
					}
				}
				if (!check) {
					++res;           // 匹配失败，划成一整段
					break;
				}
			}
			return res;
		}
};