#include <iostream>
#include <cstring>

using namespace std;

string longestCommonSubstring(string S1, string S2)
{
    int m = S1.length();
    int n = S2.length();
    int dp[m + 1][n + 1];
    memset(dp, 0, sizeof dp);

    int maxLength = 0;
    int endIndex = 0;

    for(int i = 1; i <= m; i ++ )
        for(int j = 1; j <= n; j ++ )
            if(S1[i - 1] == S2[j - 1])
            {
                dp[i][j] = dp[i - 1][j - 1] + 1;
                if(dp[i][j] > maxLength)
                {
                    maxLength = dp[i][j];
                    endIndex = i;
                }
            }

    return S1.substr(endIndex - maxLength, maxLength);
}

int main() {
    string S1 = "ABCDEF";
    string S2 = "CDEFABCDE";
    cout << "Longest Common Substring: " << longestCommonSubstring(S1, S2) << endl;
    return 0;
}