题解 | #最长公共子串#

    //动态规划，申请一个n行m列的dp数组
//dp[i][j]的含义为必须以str1[i],和str2[j]为结尾的情况下
//最长公共子串的长度是多少
#include<bits/stdc++.h>
using namespace std;
int main(){
    string  str1,str2;
    cin>>str1>>str2;
    int N=str1.size(),M=str2.size();
    int dp[N][M];//申请一个同样大的dp数组，这个dp数组一定可以包含所有的答案，填完后找到答案最大的即可
    //初始化dp数组
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++)
            dp[i][j]=-1;
    }
    int max=-1,pos=-1;//最大长度和结尾位置
    //dp数组的第一行的含义为:以str1[0]和str2[j]为结尾的情况下最长公共长度是多少
    //所以只要str1[0]==str2[j]这个位置就是1，否则就是0
    for(int i=0;i<M;i++){
        if(str1[0]==str2[i]){
            dp[0][i]=1;
            if(dp[0][i]>max){
                max=dp[0][i];
                pos=0;
            }
        }
        else dp[0][i]=0;
    }
    //dp数组的第一列同理
    for(int i=0;i<N;i++){
        if(str2[0]==str1[i]){
            dp[i][0]=1;
            if(dp[i][0]>max){
                max=dp[i][0];
                pos=i;
            }
        }
            
        else dp[i][0]=0;
    }
    //对于一个普遍位置dp[i][j]来说，根据其含义如果str1[i]==str2[j],此时dp[i][j]=dp[i-1][j-1]+1;
    //如果sttr1[i]!=str2[j],那么肯定不可能是以这两个字符作为结尾字符，所以长度是0
    for(int i=1;i<N;i++){
        for(int j=1;j<M;j++)
        {
            if(str1[i]==str2[j]){
                dp[i][j]=dp[i-1][j-1]+1;
                if(dp[i][j]>max){
                    max=dp[i][j];
                    pos=i;
                }
            }
            else dp[i][j]=0;
        }
    }
    if(pos==-1){//说明没有公共子串
        cout<<-1<<endl;
        return 0;
    }
    else{
        for(int i=pos-max+1;i<=pos;i++){
            cout<<str1[i];
        }
        return 0;
    }
}