题解 | #最长公共子串#

#include <iostream>
#include<string>
using namespace std;
string s1,s2;
int maxi=0;
int u=0;
int dp[5000][5000];
int main() {
    cin>>s1>>s2;
    int n=s1.size();
    int m=s2.size();
    for(int i=0;i<n;i++)
       if(s1[i]==s2[0])
       dp[i][0]=1;
    for(int i=0;i<m;i++)
        if(s1[0]==s2[i])
        dp[0][i]=1;
    for(int i=1;i<n;i++)
      for(int j=1;j<m;j++)
      {
        if(s1[i] ==s2[j])
        dp[i][j]=dp[i-1][j-1]+1;
      }
    for(int i=1;i<n;i++)
      for(int j=1;j<m;j++)
      {
        if(maxi<dp[i][j])
        {
             u=i;
           maxi=dp[i][j];
        }
      }
      if(maxi==0)
      {
        cout<<-1;
        return 0;
      }
      int v=maxi;
      int ma=maxi-1;
      for(int i=0;i<v;i++)
      {
            cout<<s1[u-ma];
            ma--;
      }
}
// 64 位输出请用 printf("%lld")