#include <iostream>
#include <vector>
#include <algorithm>
std::string LongestCommonSubstring(const std::string& str1, const std::string& str2) {
int m = str1.length();
int n = str2.length();
std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0));
int maxLength = 0;
int endIndex = 0;
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (str1[i - 1] == str2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
if (dp[i][j] > maxLength) {
maxLength = dp[i][j];
endIndex = i - 1;
}
} else {
dp[i][j] = 0;
}
}
}
return str1.substr(endIndex - maxLength + 1, maxLength);
}
int main() {
std::string str1 = "ABCXYZ";
std::string str2 = "XYZABC";
std::string result = LongestCommonSubstring(str1, str2);
std::cout << "Longest Common Substring: " << result << std::endl;
return 0;
}