最もシンプルで効率的な方法は、動的計画法（Dynamic Programming）を使用することです。以下に、具体的な手順を示します。
-
二次元の配列dpを用意します。dp[i][j]は、最長部分文字列の長さを表します。ここで、iは最初の文字列のインデックス、jは二つ目の文字列のインデックスを表します。
-
dpの要素を初期化します。dp[i][j]は、二つの文字列のi番目とj番目の文字が一致する場合は1、そうでない場合は0とします。
-
二重ループを使用して、dpの要素を計算します。iとjを1から文字列の長さまで順に増やしながら、以下の漸化式を適用します。
- もし、二つの文字列のi番目とj番目の文字が一致する場合（つまり、文字列が共通している場合）、dp[i][j] = dp[i-1][j-1] + 1とします。
- そうでない場合は、dp[i][j] = 0とします。
-
dpの要素の中で最大値を求めます。これが最長部分文字列の長さになります。
-
最長部分文字列の長さを使用して、元の文字列から最長部分文字列を抽出します。
以下は、上記の手順を具体的なコード例で示したものです。
#include <iostream>
#include <string>
std::string findLongestSubstring(const std::string& str1, const std::string& str2) {
int len1 = str1.length();
int len2 = str2.length();
int maxLen = 0;
int endIndex = 0;
// 二次元配列dpの初期化
int dp[len1 + 1][len2 + 1] = {0};
// dpの計算
for (int i = 1; i <= len1; i++) {
for (int j = 1; j <= len2; j++) {
if (str1[i - 1] == str2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
if (dp[i][j] > maxLen) {
maxLen = dp[i][j];
endIndex = i - 1;
}
}
}
}
// 最長部分文字列の抽出
std::string longestSubstring = str1.substr(endIndex - maxLen + 1, maxLen);
return longestSubstring;
}
int main() {
std::string str1 = "abcdef";
std::string str2 = "defgabc";
std::string longestSubstring = findLongestSubstring(str1, str2);
std::cout << "最長部分文字列: " << longestSubstring << std::endl;
return 0;
}上記のコードでは、文字列"abcdef"と"defgabc"の最長部分文字列を求める例を示しています。最長部分文字列は"abc"です。
この方法を使用することで、二つの文字列の最長部分文字列を見つけることができます。