题解 | #公共子串计算#

/*
* 给定两个只包含小写字母的字符串，计算两个字符串的最大公共子串的长度。
* 注：子串的定义指一个字符串删掉其部分前缀和后缀（也可以不删）后形成的字符串。
*/
#include <iostream>
#include <vector>
#include <string>
using namespace std;
//暴力算法
int baoliFunc(string str1, string str2)
{
	int maxlen = 0;
	string maxStr, minStr;
        //判断哪个字符串更长，哪个更短
	if (str1.length() >= str2.length()) {
		maxStr = str1;
		minStr = str2;
	}
	else {
		maxStr = str2;
		minStr = str1;
	}
        // 遍历最短的字符串的全部子串
	for (int i = 0; i < minStr.size(); i++) {
		for (int j = i + 1; j <= minStr.size(); j++) {
			string temp = minStr.substr(i, j - i);
                        // 在最长的字符串中遇到和子串第一个匹配的字符，那就截取相同长度子串进行比较
			for (int k = 0; k < maxStr.size(); k++) {
				if (maxStr[k] == temp[0] && k + temp.size() <= maxStr.size()) {
					string maxTemp = maxStr.substr(k, temp.size());
					if (maxTemp.compare(temp) == 0 && maxTemp.size() > maxlen)
						maxlen = maxTemp.size();
				}
			}
		}
	}
	return maxlen;
}
int dpFunc(string str1, string str2) {
	//思路和我们求最长递增子序列的一样，判断和上一个状态的比较
	//比如wsdfwfwe和 fwf,当第一个f相等时，就在前一状态上加1，不相等就为0；

	int n = str1.size();
	int m = str2.size();
	int max = 0;
	//初始化dp,字符串都是从下标1开始，使得初始状态都0
	// if (str[i] == str[j]) dp[i][j] = dp[i-1][j - 1] + 1;
	// else dp[i][j] = 0;
	vector<vector<int>> dp(n + 1, vector<int>(m + 1));
	for (int i = 1; i < n + 1; i++) {
		for (int j = 1; j < m + 1; j++) {
			if (str1[i - 1] == str2[j - 1]) {
				dp[i][j] = dp[i - 1][j - 1] + 1;
			}
			else
			{
				dp[i][j] = 0;
			}
			if (dp[i][j] > max)
				max = dp[i][j];
		}
	}
	return max;
}


int main()
{
	string str1, str2;
	cin >> str1 >> str2;
	cout << baoliFunc(str1, str2) << endl;
	return 0;
}