最大公共子串-蓝桥杯真题 动态规划（c++实现）

上文链接：蓝桥杯真题之“方格分裂"_DFS深度搜索(c++实现)

---

最大公共子串

有两个字符串（可能包含空格）,请找出其中最长的公共连续子串,输出其长度。
比如“qwerff”和“fqwerfo”,最大公共子串为“qwerf”，长度是5。

我的思路

1. 将字符串“qwerff”和“fqwerfo”从头开始匹配
2. 当字符串“qwerff”和“fqwerfo”匹配到q相同时，各自都向后匹配查找是否还有子串并记录公共字符串长度和比较最大长度
3. 当查到字符串“qwerff”和“fqwerfo”的公共字符‘f’时，当前长度是5，再查下一个就不匹配
4. 按照上述过程继续查找直到结束

• 动态规划思想体现在：在字符串“qwerff”和“fqwerfo”匹配到相应的字符时不用立即查找子串而是保存该记录，在之后的查找过程中在还原该子串已记录长度。算法如下。

算法展示

using namespace std;
#include <iostream>
#include <string>

int main()
{
	//定义字符串及长度 
	string str1="qwerff";
	string str2="fqwerfo";
	int lenStr1 = str1.length();
	int lenStr2 = str2.length();
	
	int max=0,count;//接受最大长度
	int tag[256][256];//定义动态规划数组 
	for(int i=1;i<=lenStr1;i++)
	{
		for(int j = 1;j<=lenStr2;j++)
		{
			//匹配到值 
			if(str1[i-1]==str2[j-1])
			{
				/*tag[i-1][j-1]在刚开始str1与str2开始匹配到时值为0，那么对应的
				 tag[i][j](即当前的最大字符长度是0+1=1，以后过程雷同)
				 */ 
				tag[i][j]= tag[i-1][j-1]+1;
				count=tag[i][j]; 
				if(count>max)max =count;//获取最大字符长度 
			}
		}
	} 
	cout<<max<<endl;
	return 0;
}