寻找最长公共子串

Scroll Down
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>

using namespace std;

pair<int, int> lcss(string &s1, string &s2) {
	if (s1.length() > s2.length()) {
		swap(s1, s2);
	}
	int m = s1.length(), n = s2.length();
	vector<vector<int>> dp(m + 1, vector<int>(n + 1));
	int res = 0;
	int end = 0;

	for (int i = 0; i <= m; i++) {
		for (int j = 0; j <= n; j++) {
			if (i == 0 || j == 0) {
				dp[i][j] = 0;
			}
			else if (s1[i - 1] == s2[j - 1]) {
				dp[i][j] = dp[i - 1][j - 1] + 1;
				if (dp[i][j] > res || (i < end && dp[i][j] == res)) {
					res = dp[i][j];
					end = i;
				}
			}
			else {
				dp[i][j] = 0;
			}
		}
	}
	return make_pair(res, end);
}
int main()
{
	string s1, s2;
	while (cin >> s1 >> s2) {
		pair<int, int> p = lcss(s1, s2);
		cout << s1.substr(p.second - p.first, p.first) << endl;
	}
	return 0;
}