【划分型动态规划 马拉车 中心扩展】2472. 不重叠回文子字符串的最大数目

如果有不明白的，请加文末QQ群。

本文涉及知识点

划分型动态规划 马拉车 中心扩展

LeetCode2472. 不重叠回文子字符串的最大数目

给你一个字符串 s 和一个 正 整数 k 。
从字符串 s 中选出一组满足下述条件且 不重叠 的子字符串：
每个子字符串的长度 至少 为 k 。
每个子字符串是一个 回文串 。
返回最优方案中能选择的子字符串的 最大 数目。
子字符串 是字符串中一个连续的字符序列。
示例 1 ：
输入：s = “abaccdbbd”, k = 3
输出：2
解释：可以选择 s = “abaccdbbd” 中斜体加粗的子字符串。“aba” 和 “dbbd” 都是回文，且长度至少为 k = 3 。
可以证明，无法选出两个以上的有效子字符串。
示例 2 ：
输入：s = “adbcda”, k = 2
输出：0
解释：字符串中不存在长度至少为 2 的回文子字符串。
提示：
1 <= k <= s.length <= 2000
s 仅由小写英文字母组成

动态规划

n = s.lenght

预备处理

利用马拉车算法，计算所有的回文，左闭右空空间。

动态规划的状态表示

dp[i]表示 s[0…i-1]的最大数目。空间复杂度：O(n)。

动态规划的转移方程

通过前置状态更新后置状态
{ d p [ i + 1 ] = m a x ( d p [ i + 1 ] , d p [ i ] ) 不选择 d p [ r ] = m a x ( d p [ r ] , d p [ i ] + 1 ) s [ l . . . r − 1 ] 是回文，且长度至少 3

$$\begin{cases} dp[i+1] = max(dp[i+1],dp[i]) && 不选择 \\ dp[r] = max(dp[r],dp[i]+1) && s[l...r-1]是回文，且长度至少3 \\ \end{cases}$$ {dp[i+1]=max(dp[i+1],dp[i])dp[r]=max(dp[r],dp[i]+1)​​不选择s[l...r−1]是回文，且长度至少3​
单个状态转移的时间复杂度: O(n)，总时间复杂度：O(nn)

动态规划的初始值

全部为0

动态规划的填表顺序

i = 0 to n-1

动态规划的返回值

dp.back()

代码

核心代码

template<class ELE>
void MaxSelf(ELE* seft, const ELE& other)
{
	*seft = max(*seft, other);
}
//马拉车计算回文回文
class CPalindrome
{
public:
	void  CalCenterHalfLen(const string& s)
	{
		vector<char> v = { '*' };
		for (const auto& ch : s)
		{
			v.emplace_back(ch);
			v.emplace_back('*');
		}

		const int len = v.size();
		vector<int> vHalfLen(len);
		int center = -1, r = -1;
		//center是对称中心,r是其右边界（闭）
		for (int i = 0; i < len; i++)
		{
			int tmp = 1;
			if (i <= r)
			{
				int pre = center - (i - center);
				tmp = min(vHalfLen[pre], r - i + 1);
			}
			for (tmp++; (i + tmp - 1 < len) && (i - tmp + 1 >= 0) && (v[i + tmp - 1] == v[i - tmp + 1]); tmp++);
			vHalfLen[i] = --tmp;
			const int iNewR = i + tmp - 1;
			if (iNewR > r)
			{
				r = iNewR;
				center = i;
			}
		}

		m_vOddCenterHalfLen.resize(s.length());
		m_vEvenCenterHalfLen.resize(s.length());
		for (int i = 1; i < len; i++)
		{
			const int center = (i - 1) / 2;
			const int iHalfLen = vHalfLen[i] / 2;
			if (i & 1)
			{//原字符串奇数长度
				m_vOddCenterHalfLen[center] = iHalfLen;
			}
			else
			{
				m_vEvenCenterHalfLen[center] = iHalfLen;
			}
		}
	}
	/// <summary>
	/// 获取所有回文子串，左闭右开空间
	/// </summary>
	/// <param name="s">ret[i]升序。ret[i]如果包括j，则s[i...j-1]是回文</param>
	/// <returns></returns>
	vector<vector<int>> CalLeftRightExinc(const string& s)
	{
		vector<vector<int>> ret(s.length());
		CalCenterHalfLen(s);
		for (int i = 0; i < m_vOddCenterHalfLen.size(); i++) {
			{
				const int& lenMax = m_vOddCenterHalfLen[i];
				for (int len = 1; len <= lenMax; len++) {
					ret[i - len + 1].emplace_back(i + len);
				}
			}
			{//不能循环两次，否则结果不一定升序
				const int& lenMax = m_vEvenCenterHalfLen[i];
				for (int len = 1; len <= lenMax; len++) {
					ret[i - len + 1].emplace_back(i + 1 + len);
				}
			}
		}
		return ret;
	}
	vector<int> m_vOddCenterHalfLen, m_vEvenCenterHalfLen;//vOddHalfLen[i]表示 以s[i]为中心，且长度为奇数的最长回文的半长，包括s[i]
	//比如："aba" vOddHalfLen[1]为2 "abba" vEvenHalfLen[1]为2
};


class Solution {
public:
	int maxPalindromes(string s, int k) {
		CPalindrome pd;
		auto lr = pd.CalLeftRightExinc(s);
		const int N = s.length();
		vector<int> dp(N + 1);
		for (int i = 0; i < N; i++) {
			MaxSelf(&dp[i + 1], dp[i]);
			for (const auto& r : lr[i]) {
				if (r - i < k) { continue; }
				MaxSelf(&dp[r], dp[i] + 1);
			}
		}
		return dp.back();
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103

单元测试

template<class T1, class T2>
void AssertEx(const T1& t1, const T2& t2)
{
	Assert::AreEqual(t1, t2);
}

template<class T>
void AssertEx(const vector<T>& v1, const vector<T>& v2)
{
	Assert::AreEqual(v1.size(), v2.size());
	for (int i = 0; i < v1.size(); i++)
	{
		Assert::AreEqual(v1[i], v2[i]);
	}
}

template<class T>
void AssertV2(vector<vector<T>> vv1, vector<vector<T>> vv2)
{
	sort(vv1.begin(), vv1.end());
	sort(vv2.begin(), vv2.end());
	Assert::AreEqual(vv1.size(), vv2.size());
	for (int i = 0; i < vv1.size(); i++)
	{
		AssertEx(vv1[i], vv2[i]);
	}
}

namespace UnitTest
{	
	string s;
	int k;
	TEST_CLASS(UnitTest)
	{
	public:
		TEST_METHOD(TestMethod00)
		{
			s = "abaccdbbd", k = 3;
			auto res = Solution().maxPalindromes(s, k);
			AssertEx(2, res);
		}
		TEST_METHOD(TestMethod01)
		{
			s = "adbcda", k = 2;
			auto res = Solution().maxPalindromes(s, k);
			AssertEx(0, res);
		}

	};
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

扩展阅读

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关推荐

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。