算法学习之最长公共子串

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;

void get_lcs(char *str1,char *str2)
{
    int n1 = strlen(str1);
    int n2 = strlen(str2);
    int dp[n1][n2];  //存各个状态数据
    int maxdata = 0; //保存最大的那个长度
    int resulti;
    for(int j = 0; j < n2; j++)
        dp[0][j] = (str1[0] == str2[j] ? 1 : 0); //初始化str1只有一个字符的情况；
    for(int i = 1; i < n1; i++)
    {
        dp[i][0] = (str1[i] == str2[0] ? 1 : 0); //str2只有一个字符的情况
        for(int j = 1; j < n2; j++)
        {
            if(str1[i] == str2[j])  //如果两个字符相等
            {
                dp[i][j] = dp[i-1][j-1]+1;
                if(dp[i][j] > maxdata) //如果求得的值大于最大值则交换
                {
                    maxdata = dp[i][j];
                    resulti = i;
                }
            }
            else
                dp[i][j] = 0;  //如果不相等这个状态置0；
        }
    }
    printf("%d\n",maxdata);
    for(int i = resulti - maxdata+1; i <= resulti; i++)
        printf("%c",str1[i]);
}
int main()
{
    char str1[1000];
    char str2[1000];
    scanf("%s",str1);
    scanf("%s",str2);
    get_lcs(str1,str2);
    return 0;
}