【KMP】P7114 [NOIP2020] 字符串匹配|省选-

本文涉及知识点

较难理解的字符串查找算法KMP

P7114 [NOIP2020] 字符串匹配

题目描述

小 C 学习完了字符串匹配的相关内容，现在他正在做一道习题。

对于一个字符串 $S$，题目要求他找到 $S$ 的所有具有下列形式的拆分方案数：

$S=ABC$，$S=ABABC$，$S=ABAB\dots ABC$，其中 $A$，$B$，$C$ 均是非空字符串，且 $A$ 中出现奇数次的字符数量不超过 $C$ 中出现奇数次的字符数量。

更具体地，我们可以定义 $AB$ 表示两个字符串 $A$，$B$ 相连接，例如 $A=\text{aab}$，$B=\text{ab}$，则 $AB=\text{aabab}$。

并递归地定义 $A^1=A$，$A^n=A^{n-1}A$（$n\ge 2$ 且为正整数）。例如 $A=\text{abb}$，则 $A^3=\text{abbabbabb}$。

则小 C 的习题是求 $S={(AB)}^{i}C$ 的方案数，其中 $F(A)\le F(C)$，$F(S)$ 表示字符串 $S$ 中出现奇数次的字符的数量。两种方案不同当且仅当拆分出的 $A$、$B$、$C$ 中有至少一个字符串不同。

小 C 并不会做这道题，只好向你求助，请你帮帮他。

输入格式

本题有多组数据，输入文件第一行一个正整数 $T$ 表示数据组数。

每组数据仅一行一个字符串 $S$，意义见题目描述。$S$ 仅由英文小写字母构成。

输出格式

对于每组数据输出一行一个整数表示答案。

输入输出样例 #1

输入 #1

3
nnrnnr
zzzaab
mmlmmlo

输出 #1

8
9
16

输入输出样例 #2

输入 #2

5
kkkkkkkkkkkkkkkkkkkk
lllllllllllllrrlllrr
cccccccccccccxcxxxcc
ccccccccccccccaababa
ggggggggggggggbaabab

输出 #2

156
138
138
147
194

输入输出样例 #3

输入 #3

见附件中的 string/string3.in

输出 #3

见附件中的 string/string3.ans

输入输出样例 #4

输入 #4

见附件中的 string/string4.in

输出 #4

见附件中的 string/string4.ans

说明/提示

【样例 #1 解释】

对于第一组数据，所有的方案为

1. $A=\text{n}$，$B=\text{nr}$，$C=\text{nnr}$。
2. $A=\text{n}$，$B=\text{nrn}$，$C=\text{nr}$。
3. $A=\text{n}$，$B=\text{nrnn}$，$C=\text{r}$。
4. $A=\text{nn}$，$B=\text{r}$，$C=\text{nnr}$。
5. $A=\text{nn}$，$B=\text{rn}$，$C=\text{nr}$。
6. $A=\text{nn}$，$B=\text{rnn}$，$C=\text{r}$。
7. $A=\text{nnr}$，$B=\text{n}$，$C=\text{nr}$。
8. $A=\text{nnr}$，$B=\text{nn}$，$C=\text{r}$。

【数据范围】

测试点编号	$|S|\le$	特殊性质
$1\sim 4$	$10$	无
$5\sim 8$	$100$	无
$9\sim 12$	$1000$	无
$13\sim 14$	$2^{15}$	$S$ 中只包含一种字符
$15\sim 17$	$2^{16}$	$S$ 中只包含两种字符
$18\sim 21$	$2^{17}$	无
$22\sim 25$	$2^{20}$	无

对于所有测试点，保证 $1\le T\le 5$，$1\le |S|\le 2^{20}$。

P7114 扩展KMP 树状数组 |省选-

z是s的z函数。
枚举AB是s[0…m-1]，在不限制$F(A)$和$F(C)$的情况下，$(AB{)}^i$，i的最大值是i1。当i取i1是，余下的部分是C1。
如果i = i2,则C= $(AB{)}^{i1-i2}$C1 ,如果i1-i2是偶数，则F©=F(C1);否则F©=F(ABC1)

子问题一：利用扩展KMP求i1

如果$A^i$成立，则利用KMP判断$A^{2i}$是否成立，如果成立，继续判断$A^{4i}$；否则判断$A^i到A^{2i}$。
封装成函数：Check(begin)，i =m ; （i+begin < n)其(z[i+begin]>=i) ; i+=i 。如果 i >= n，说明s由n/m个AB组成。如果m ==i，则i1= 1。否则Check2(i-m)。
求is[i]的时间复杂度是：O(lognlogn)，故总时间复杂度O(nlognlogn)。

思路

fa[i]记录s长度为i的前缀，出现奇数次字母的数量。fc[i]记录s长度为i的后缀出现奇数次字母的数量。
因为C不能为空。故如果i1m = n，则 i$\in$[1,i1-1]，否则i$\in$[1,i1]。
i3是i2为奇数的数量，i4=F(ABC1)。i5=treeArr[0…i4]。 ans += i3i5。
i6是i2为偶数的数量，i7=F(C1),i8=treeArr[0…i7]。ans += i6i8。
只需要计算质数m
如果m2 > m1，则 $m2\times i12\le m1\times i11$,即i12 = i11m1/m2,当i12为1时，例外。

优化

z[i] = k , i1一定大于等于1，故从2枚举起。
如果i1 >=2 ,则z[i]一定大于等于i。反之也成立。
如果i1 >= 3，则z[2i]一定大于等于i。即z[i] >=2i。
猜想：
z[i] >= i1*i，则一定有i1个循环节。z[i] >= i ，则：s[0…i)== s[i…2i) 公式一，z[i] >= 2i s[i…2i)=s[2i…3i)公式二，公式一结合公式二，s[0…i]等于s[2i…3i)。更大的i1类似，反推类似。
即i1 = z[i]/i。
时间复杂度：O(n)

代码

核心代码

#include <iostream>
#include <sstream>
#include <vector>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<string>
#include<algorithm>
#include<functional>
#include<queue>
#include <stack>
#include<iomanip>
#include<numeric>
#include <math.h>
#include <climits>
#include<assert.h>
#include<cstring>
#include<list>#include <bitset>
using namespace std;template<class T1, class T2>
std::istream& operator >> (std::istream& in, pair<T1, T2>& pr) {in >> pr.first >> pr.second;return in;
}template<class T1, class T2, class T3 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3>& t) {in >> get<0>(t) >> get<1>(t) >> get<2>(t);return in;
}template<class T1, class T2, class T3, class T4 >
std::istream& operator >> (std::istream& in, tuple<T1, T2, T3, T4>& t) {in >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t);return in;
}template<class T = int>
vector<T> Read() {int n;cin >> n;vector<T> ret(n);for (int i = 0; i < n; i++) {cin >> ret[i];}return ret;
}
template<class T = int>
vector<T> ReadNotNum() {vector<T> ret;T tmp;while (cin >> tmp) {ret.emplace_back(tmp);if ('\n' == cin.get()) { break; }}return ret;
}template<class T = int>
vector<T> Read(int n) {vector<T> ret(n);for (int i = 0; i < n; i++) {cin >> ret[i];}return ret;
}template<int N = 1'000'000>
class COutBuff
{
public:COutBuff() {m_p = puffer;}template<class T>void write(T x) {int num[28], sp = 0;if (x < 0)*m_p++ = '-', x = -x;if (!x)*m_p++ = 48;while (x)num[++sp] = x % 10, x /= 10;while (sp)*m_p++ = num[sp--] + 48;AuotToFile();}void writestr(const char* sz) {strcpy(m_p, sz);m_p += strlen(sz);AuotToFile();}inline void write(char ch){*m_p++ = ch;AuotToFile();}inline void ToFile() {fwrite(puffer, 1, m_p - puffer, stdout);m_p = puffer;}~COutBuff() {ToFile();}
private:inline void AuotToFile() {if (m_p - puffer > N - 100) {ToFile();}}char  puffer[N], * m_p;
};template<int N = 1'000'000>
class CInBuff
{
public:inline CInBuff() {}inline CInBuff<N>& operator>>(char& ch) {FileToBuf();ch = *S++;return *this;}inline CInBuff<N>& operator>>(int& val) {FileToBuf();int x(0), f(0);while (!isdigit(*S))f |= (*S++ == '-');while (isdigit(*S))x = (x << 1) + (x << 3) + (*S++ ^ 48);val = f ? -x : x; S++;//忽略空格换行		return *this;}inline CInBuff& operator>>(long long& val) {FileToBuf();long long x(0); int f(0);while (!isdigit(*S))f |= (*S++ == '-');while (isdigit(*S))x = (x << 1) + (x << 3) + (*S++ ^ 48);val = f ? -x : x; S++;//忽略空格换行return *this;}template<class T1, class T2>inline CInBuff& operator>>(pair<T1, T2>& val) {*this >> val.first >> val.second;return *this;}template<class T1, class T2, class T3>inline CInBuff& operator>>(tuple<T1, T2, T3>& val) {*this >> get<0>(val) >> get<1>(val) >> get<2>(val);return *this;}template<class T1, class T2, class T3, class T4>inline CInBuff& operator>>(tuple<T1, T2, T3, T4>& val) {*this >> get<0>(val) >> get<1>(val) >> get<2>(val) >> get<3>(val);return *this;}template<class T = int>inline CInBuff& operator>>(vector<T>& val) {int n;*this >> n;val.resize(n);for (int i = 0; i < n; i++) {*this >> val[i];}return *this;}template<class T = int>vector<T> Read(int n) {vector<T> ret(n);for (int i = 0; i < n; i++) {*this >> ret[i];}return ret;}template<class T = int>vector<T> Read() {vector<T> ret;*this >> ret;return ret;}
private:inline void FileToBuf() {const int canRead = m_iWritePos - (S - buffer);if (canRead >= 100) { return; }if (m_bFinish) { return; }for (int i = 0; i < canRead; i++){buffer[i] = S[i];//memcpy出错			}m_iWritePos = canRead;buffer[m_iWritePos] = 0;S = buffer;int readCnt = fread(buffer + m_iWritePos, 1, N - m_iWritePos, stdin);if (readCnt <= 0) { m_bFinish = true; return; }m_iWritePos += readCnt;buffer[m_iWritePos] = 0;S = buffer;}int m_iWritePos = 0; bool m_bFinish = false;char buffer[N + 10], * S = buffer;
};class KMP
{
public:virtual int Find(const string& s, const string& t){CalLen(t);for (int i1 = 0, j = 0; i1 < s.length(); ){for (; (j < t.length()) && (i1 + j < s.length()) && (s[i1 + j] == t[j]); j++);//i2 = i1 + j 此时s[i1,i2)和t[0,j)相等 s[i2]和t[j]不存在或相等//t[0,j)的结尾索引是j-1，所以最长公共前缀为m_vLen[j-1]，简写为y 则t[0,y)等于t[j-y,j)等于s[i2-y,i2)if (0 == j){i1++;continue;}const int i2 = i1 + j;j = m_vLen[j - 1];i1 = i2 - j;//i2不变}return -1;}//vector<int> m_vSameLen;//m_vSame[i]记录 s[i...]和t[0...]最长公共前缀，增加可调试性 部分m_vSameLen[i]会缺失//static vector<int> Next(const string& s)//{// j = vNext[i] 表示s[0,i]的最大公共前后缀是s[0,j]//	const int len = s.length();//	vector<int> vNext(len, -1);//	for (int i = 1; i < len; i++)//	{//		int next = vNext[i - 1];//		while ((-1 != next) && (s[next + 1] != s[i]))//		{//			next = vNext[next];//		}//		vNext[i] = next + (s[next + 1] == s[i]);//	}//	return vNext;//}const vector<int> CalLen(const string& str){m_vLen.resize(str.length());for (int i = 1; i < str.length(); i++){int next = m_vLen[i - 1];while (str[next] != str[i]){if (0 == next){break;}next = m_vLen[next - 1];}m_vLen[i] = next + (str[next] == str[i]);}return m_vLen;}
protected:int m_c;vector<int> m_vLen;//m_vLen[i] 表示str[0,i]的最长公共前后缀的长度
};template<long long MOD = 1000000007, class T1 = int, class T2 = long long>
class C1097Int
{
public:C1097Int(T1 iData = 0) :m_iData(iData% MOD){}C1097Int(T2 llData) :m_iData(llData% MOD) {}C1097Int  operator+(const C1097Int& o)const{return C1097Int(((T2)m_iData + o.m_iData) % MOD);}C1097Int& operator+=(const C1097Int& o){m_iData = ((T2)m_iData + o.m_iData) % MOD;return *this;}C1097Int& operator-=(const C1097Int& o){m_iData = ((T2)MOD + m_iData - o.m_iData) % MOD;return *this;}C1097Int  operator-(const C1097Int& o){return C1097Int(((T2)MOD + m_iData - o.m_iData) % MOD);}C1097Int  operator*(const C1097Int& o)const{return((T2)m_iData * o.m_iData) % MOD;}C1097Int& operator*=(const C1097Int& o){m_iData = ((T2)m_iData * o.m_iData) % MOD;return *this;}C1097Int  operator/(const C1097Int& o)const{return *this * o.PowNegative1();}C1097Int& operator/=(const C1097Int& o){*this /= o.PowNegative1();return *this;}bool operator==(const C1097Int& o)const{return m_iData == o.m_iData;}bool operator<(const C1097Int& o)const{return m_iData < o.m_iData;}C1097Int pow(T2 n)const{C1097Int iRet = (T1)1, iCur = *this;while (n){if (n & 1){iRet *= iCur;}iCur *= iCur;n >>= 1;}return iRet;}C1097Int PowNegative1()const{return pow(MOD - 2);}T1 ToInt()const{return ((T2)m_iData + MOD) % MOD;}
private:T1 m_iData = 0;;
};class CParentToNeiBo
{
public:CParentToNeiBo(const vector<int>& parents){m_vNeiBo.resize(parents.size());for (int i = 0; i < parents.size(); i++){if (-1 == parents[i]){m_root = i;}else{m_vNeiBo[parents[i]].emplace_back(i);}}}vector<vector<int>> m_vNeiBo;int m_root = -1;
};
class CBFSLeve {
public:static vector<int> Leve(const vector<vector<int>>& neiBo, vector<int> start) {vector<int> leves(neiBo.size(), -1);for (const auto& s : start) {leves[s] = 0;}for (int i = 0; i < start.size(); i++) {for (const auto& next : neiBo[start[i]]) {if (-1 != leves[next]) { continue; }leves[next] = leves[start[i]] + 1;start.emplace_back(next);}}return leves;}template<class NextFun>static vector<int> Leve(int N, NextFun nextFun, vector<int> start) {vector<int> leves(N, -1);for (const auto& s : start) {leves[s] = 0;}for (int i = 0; i < start.size(); i++) {auto nexts = nextFun(start[i]);for (const auto& next : nexts) {if (-1 != leves[next]) { continue; }leves[next] = leves[start[i]] + 1;start.emplace_back(next);}}return leves;}static vector<vector<int>> LeveNodes(const vector<int>& leves) {const int iMaxLeve = *max_element(leves.begin(), leves.end());vector<vector<int>> ret(iMaxLeve + 1);for (int i = 0; i < leves.size(); i++) {ret[leves[i]].emplace_back(i);}return ret;};static vector<int> LeveSort(const vector<int>& leves) {const int iMaxLeve = *max_element(leves.begin(), leves.end());vector<vector<int>> leveNodes(iMaxLeve + 1);for (int i = 0; i < leves.size(); i++) {leveNodes[leves[i]].emplace_back(i);}vector<int> ret;for (const auto& v : leveNodes) {ret.insert(ret.end(), v.begin(), v.end());}return ret;};
};class CParents
{
public:CParents(vector<int>& vParent, const int iMaxDepth){int iBitNum = 0;for (; (1 << iBitNum) < iMaxDepth; iBitNum++);const int n = vParent.size();m_vParents.assign(iBitNum + 1, vector<int>(n, -1));m_vParents[0] = vParent;//树上倍增for (int i = 1; i < m_vParents.size(); i++){for (int j = 0; j < n; j++){const int iPre = m_vParents[i - 1][j];if (-1 != iPre){m_vParents[i][j] = m_vParents[i - 1][iPre];}}}}int GetParent(int iNode, int iDepth)const{int iParent = iNode;for (int iBit = 0; iBit < m_vParents.size(); iBit++){if (-1 == iParent){return iParent;}if (iDepth & (1 << iBit)){iParent = m_vParents[iBit][iParent];}}return iParent;}inline int GetBitCnt()const { return m_vParents.size(); };inline const int& GetPow2Parent(int iNode, int n)const {return m_vParents[n][iNode];}//在leftNodeExclude的1到rightLeve级祖先中查找符合pr的最近祖先template<class _Pr>int FindFirst(int leftNodeExclude, int rightLeve, _Pr pr) {for (int iBit = GetBitCnt() - 1; iBit >= 0; iBit--) {const int iMask = 1 << iBit;if (!(iMask & rightLeve)) { continue; }if (pr(m_vParents[iBit][leftNodeExclude])) {return BFindFirst(leftNodeExclude, iBit, pr);}leftNodeExclude = m_vParents[iBit][leftNodeExclude];}return -1;}
protected://在leftNodeExclude的1到2^pow^级祖先中查找符合pr的最近祖先template<class _Pr>int BFindFirst(int leftNodeExclude, int pow, _Pr pr) {while (pow > 0) {const int& mid = m_vParents[pow - 1][leftNodeExclude];if (pr(mid)) {}else {leftNodeExclude = mid;}pow--;}return m_vParents[0][leftNodeExclude];}vector<vector<int>> m_vParents;
};
class KMPEx
{
public:static vector<int> ZFunction(string s) {int n = (int)s.length();vector<int> z(n);z[0] = n;for (int i = 1, left = 0, r = 0; i < n; ++i) {if (i <= r) {//如果此if,r-i+1可能为负数z[i] = min(z[i - left], r - i + 1);}while ((i + z[i] < n) && (s[z[i]] == s[i + z[i]])) {z[i]++;}if (i + z[i] - 1 > r) left = i, r = i + z[i] - 1;}return z;//z[i] 表示S与其后缀S[i,n]的最长公共前缀(LCP)的长度}static int MinCyc(const string& str, int unit = 1) {const int N = str.length();auto z = ZFunction(str);auto Is = [&](int k) {for (int i = k; i < N; i <<= 1) {if (z[i] < min(N - i, i)) { return false; }}return true;};for (int k = unit; k < N; k += unit) { if (Is(k))return k; }return N;}};
template<class ELE = int >
class ITreeArrSumOpe
{
public:virtual void Assign(ELE& dest, const ELE& src) = 0;virtual ELE Back(const ELE& n1, const ELE& n2) = 0;
};template<class ELE = int >
class CTreeArrAddOpe :public ITreeArrSumOpe<ELE>
{
public:virtual void Assign(ELE& dest, const ELE& src) {dest += src;}virtual ELE Back(const ELE& n1, const ELE& n2) {return n1 - n2;}
};template<class ELE = int, class ELEOpe = CTreeArrAddOpe<ELE> >
class CTreeArr
{
public:CTreeArr(int iSize) :m_vData(iSize + 1){}void Add(int index, ELE value){if ((index < 0) || (index >= m_vData.size() - 1)) { return; }index++;while (index < m_vData.size()){m_ope.Assign(m_vData[index], value);index += index & (-index);}}ELE Sum(int index)//[0...index]之和{index++;ELE ret = 0;while (index){m_ope.Assign(ret, m_vData[index]);index -= index & (-index);}return ret;}ELE Sum() { return Sum(m_vData.size() - 2); }ELE Get(int index){return m_ope.Back(Sum(index), Sum(index - 1));}
private:ELEOpe m_ope;vector<ELE> m_vData;
};
class Solution {
public:long long Ans(const string& str) {const int N = str.length();vector<int> is(N, -1);auto z = KMPEx::ZFunction(str);for (int m = 2; m < N; m++) {is[m] = z[m] / m + 1;}auto F = [&](const auto& str) {int cnt[26] = { 0 };vector<int> fa = { 0 };int iCnt = 0;for (const auto& ch : str) {cnt[ch - 'a']++;if (1 & cnt[ch - 'a']) {iCnt++;}else {iCnt--;}fa.emplace_back(iCnt);}return fa;};auto fa = F(str);auto fc = F(string(str.rbegin(), str.rend()));CTreeArr<int> treeArr(N);long long ans = 0;for (int m = 2; m < N; m++) {//不考虑0，i2取值[1...i2]int i2 = is[m] - 1;int i6 = i2 / 2;const int i3 = i2 - i6;if (is[m] * m != N) {i6++;//取0}treeArr.Add(fa[m - 1], 1);//i6是i2为偶数的数量，i7=F(C1),i8=treeArr[0...i7]。ans += i6*i8。					const int i7 = fc[N - m * is[m]];const long long i8 = treeArr.Sum(i7);//i3是i2为奇数的数量，i4 = F(ABC1)。i5 = treeArr[0...i4]。 ans += i3 * i5。	const int i4 = fc[N - m * (is[m] - 1)];const long long i5 = treeArr.Sum(i4);ans += i6 * i8;ans += i3 * i5;}return ans;}
};int main() {
#ifdef _DEBUGfreopen("a.in", "r", stdin);
#endif // DEBUG	ios::sync_with_stdio(0); cin.tie(nullptr);int T;cin >>T     ;for (int i = 0; i < T; i++) {string s;cin >> s;auto res = Solution().Ans(s);cout << res << "\n";}#ifdef _DEBUG		//printf("n=%d",n);//Out(rang, ",rang=");//Out(edge, ",edge=");/*Out(que, "que=");*/
#endif // DEBUG		return 0;
}

单元测试

	TEST_METHOD(TestMethod1){auto res = Solution().Ans("nnrnnr");AssertEx(8LL, res);}TEST_METHOD(TestMethod2){auto res = Solution().Ans("zzzaab");AssertEx(9LL, res);}TEST_METHOD(TestMethod3){auto res = Solution().Ans("mmlmmlo");AssertEx(16lL, res);}TEST_METHOD(TestMethod4){auto res = Solution().Ans("kkkkkkkkkkkkkkkkkkkk");AssertEx(156LL, res);}TEST_METHOD(TestMethod5){auto res = Solution().Ans("lllllllllllllrrlllrr");AssertEx(138LL, res);}TEST_METHOD(TestMethod6){auto res = Solution().Ans("cccccccccccccxcxxxcc");AssertEx(138LL, res);}TEST_METHOD(TestMethod7){auto res = Solution().Ans("ccccccccccccccaababa");AssertEx(147LL, res);}TEST_METHOD(TestMethod8){auto res = Solution().Ans("ggggggggggggggbaabab");AssertEx(194LL, res);}

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标 及时的反馈 拉伸区（难度合适） 专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功 成功+反思=成功

视频课程

先学简单的课程，请移步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++**实现。

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标 及时的反馈 拉伸区（难度合适） 专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功 成功+反思=成功

视频课程

先学简单的课程，请移步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++**实现。