ダイナミックプランニング-最長共通サブストリング

dp[i][j]は、共通サブストリングの最後のアルファベットがstr 1[i]およびstr 2[j]である場合の共通サブストリングの長さとする.
状態遷移方程式:

str 1[i]==str 2[j]のとき、dp[i][j]=dp[i-1][j-1]+1;

str 1[i]!=str 2[j]の場合、dp[i][j]=0; 

#include
#include
#include 
using namespace std;

int findMaxSubstring(const char* str1, const char* str2)
{
    int dp[100][100];
    int len1 = strlen(str1);
    int len2 = strlen(str2);

    for (int i = 0; i < len1; i++)
    {
        if (str1[i] == str2[0])
        {
            dp[i][0] = 1;
        }
        else
        {
            dp[i][0] = 0;
        }
    }

    for (int j = 0; j < len2; j++)
    {
        if (str1[0] == str2[j])
        {
            dp[0][j] = 1;
        }
        else
        {
            dp[0][j] = 0;
        }
    }

    int maxLen = 0;
    int endIndex = 0;
    for (int i = 1; i < len1; i++)
    {
        for (int j = 1; j < len2; j++)
        {
            if (str1[i] == str2[j])
            {
                dp[i][j] = dp[i - 1][j - 1] + 1;
                if (maxLen < dp[i][j])
                {
                    maxLen = dp[i][j];
                    endIndex = i;
                }
            }
            else
            {
                dp[i][j] = 0;
            }
        }
    }

    for (int i = endIndex - maxLen + 1; i <= endIndex; i++)
    {
        cout << str1[i];
    }
    cout << endl;
    return maxLen;
}

int main()
{
    char str1[100];
    char str2[100];
    gets(str1);
    gets(str2);
    
    int maxlen = findMaxSubstring(str1, str2);
    cout << maxlen << endl;
    return 0;
}

参考文献:
この文章には最適化アルゴリズムが含まれている:『最長共通サブストリングの動的計画解法とその最適化』