题目描述
查找两个字符串a,b中的最长公共子串。若有多个，输出在较短串中最先出现的那个。
输入描述:
输入两个字符串输出描述:
返回重复出现的字符示例1
输入
abcdefghijklmnop
abcsafjklmnopqrstuvw输出
jklmnop算法实现
// 暴力
#include <iostream>
#include <string>
#include <vector>
using namespace std;
#define MaxShowNum 4std::string Fun(std::string& s1,std::string& s2)
{std::string ss1, ss2;// ss1较短s1.size() < s2.size() ? (ss1 = s1,ss2 = s2) : (ss1 = s2,ss2 = s1);for (int i = 1; i <= ss1.size(); ++i){int n = i;for (int j = 0; j < n; ++j){std::string s = ss1.substr(j, ss1.size() - n + 1);// 截取此次i循环的，子串最大长度if (ss2.find(s) != string::npos)// 找子串return s;}}
}
// 动态规划(二维数组存以该字符为结尾的最大子串的长度)
/*0 1 2 3 4 5 6 7a b c d e f g
0 0 0 0 0 0 0 0 0
1 b 0 0 1 0 0 0 0 0
2 c 0 0 0 2 0 0 0 0
3 d 0 0 0 0 3 0 0 0
// 连续的肯定是斜的，即如果连续的字符串是"bc"，则b:[1][2]和c:[2][3]是有数据的,因为和前一个字符连续，所以b[i - 1][j - 1] + 1= c[i][j]
*/
std::string Fun1(std::string& s1, std::string& s2)
{if (s1.size() > s2.size())// s1存短的std::swap(s1, s2);int s1_size = s1.size(), s2_size = s2.size();int maxLen = 0;int begIdx = 0;std::vector<std::vector<int>> dp(s1_size + 1, std::vector<int>(s2_size + 1, 0));for (int i = 1; i <= s1_size; ++i){for (int j = 1; j <= s2_size; ++j){if (s1[i - 1] == s2[j - 1]){dp[i][j] = dp[i - 1][j - 1] + 1;// 这个if放到外面这个if下面也行if (maxLen < dp[i][j]){maxLen = dp[i][j];// begIdx = j - maxLen;// 对应 s2.substr(begIdx, maxLen);begIdx = i - maxLen;// 对应 s1.substr(begIdx, maxLen);}}}}return s1.substr(begIdx, maxLen);
}int main()
{std::string s1,s2;while (std::cin >> s1 >> s2){std::cout << Fun1(s1, s2) << std::endl;}return 0;
}