#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int dp[5010][5010],dpr[5010];
int main(){
    char str1[5010],str2[5010];
    scanf("%s %s",str1+1,str2+1);
    int maxlen=0,maxend=0;
    int len1=strlen(str1+1);
    int len2=strlen(str2+1);
    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;  //dp[i][j]表示以i，j为尾的最长公共子串的长度（连续）
                 if(maxlen<dp[i][j])
                 {
                     maxlen=dp[i][j];
                     maxend=i;
                 }   
            }
        }
    }
    if (maxlen == 0)
    {
        printf("-1");
        return 0;
    }
    for(int i=maxend-maxlen+1;i<=maxend;i++){
        printf("%c",str1[i]);
    }
    return 0;
    //printf("%d",dp[strlen(str1)][strlen(str2)]);
}

#include <bits/stdc++.h>
using namespace std;
int main(){
    string a, b;
    cin>>a>>b;
    int n=a.length(), m=b.length();
    int dp[n+1][m+1], Max=0, l;
    memset(dp, 0, sizeof(dp));
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++){
            if(a[i]==b[j]){
                dp[i+1][j+1] = dp[i][j] + 1;
                if(Max < dp[i+1][j+1]){
                    Max = dp[i+1][j+1];
                    l = i+1;
                }
            }else
                dp[i+1][j+1] = 0;
        }
    if(Max==0)
        cout<<-1<<endl;
    else{
        for(int i=l-Max;i<=l-1;i++)
            cout<<a[i];
    }
    return 0;
}

#include<iostream>
#include<string>
using namespace std;

void findLCStr(string A, int n, string B, int m) {
    int c[n+1][m+1];
    int i,j,res=0,res_end;//res 最长公共子串长度，res_end最长公共子串末尾序号
    for(i=0;i<=n;i++) c[i][0]=0;
    for(j=1;j<=m;j++) c[0][j]=0;

    for(i=1;i<=n;i++){
        for(j=1;j<=m;j++){
            if(A[i-1]==B[j-1]){
                c[i][j] = c[i-1][j-1] + 1;
                if(res<c[i][j]){
                    res = c[i][j];
                    res_end = i;
                }
                //res = max(res, c[i][j]);
            }
            else c[i][j] = 0;    //与LCS的区别在这里
        }
    }
    if(res==0) cout<<-1<<endl;
    else{
        for(i=res_end-1-res+1;i<=res_end-1;++i)
            cout<<A[i];
        cout<<endl;
    }
}
int main(){
    string A,B;
    cin>>A>>B;
    findLCStr(A,A.length(),B,B.length());
}

#include <iostream>
#include <vector>
#include <string>
#include <stack>//T6
#include <map>

using namespace std;


//最长公共子串，dp二维矩阵，dp[i][j] = dp[i-1][j-1],因为要求连续
//搞清楚dp[i][j]的含义
//注意更新maxLen和maxEnd时，要搞清楚dp[i][j] 表示的是以s1[i]，s2[j]“结尾”的公共子串的长度
//因此每一个dp[i][j]都要和maxLen比较一下，然后存起来maxLen和maxEnd
//矩阵右下角的dp[i][j]代表以s1末尾，s2末尾结尾的公共子串的长度，可以为0，而公共子串不一定非要以s1末尾，s2末尾结尾

int main()
{
	string s1, s2;
	cin >> s1 >> s2;
	vector< vector<int>> dp(s1.length(), vector<int>(s2.length(), 0));
	for (int j = 0; j < s2.length(); j++)
		if(s1[0]==s2[j])
			dp[0][j] = 1;
	for (int i = 0; i < s1.length(); i++)
		if (s1[i] == s2[0])
			dp[i][0] = 1;
	int maxLen = 0, maxEnd = 0;
	for (int i = 1; i < s1.length(); i++)
	{
		for (int j = 1; j < s2.length(); j++)
		{
			if (s1[i] == s2[j])
				dp[i][j] = dp[i - 1][j - 1] + 1;
			if (dp[i][j] > maxLen)
			{
				maxLen = dp[i][j];
				maxEnd = i;
			}
		}		
	}
	if (maxLen == 0)
	{
		cout << -1;
		return 0;
	}
	else
	{
		for (int i = maxEnd - maxLen + 1; i <= maxEnd; i++)
			cout << s1[i];
	}
	
	system("pause");
	return 0;
}

/**
**		后缀自动机模板题，有兴趣可以学一下
**		可以快速处理一些字符串题 例如
**		10个长度100000串的最长公共子串 
**		出现次数有限制（比如出现次数为k次）的子串 
**      author:XiaKIsGod
**      time:2019.9
**/
#include <bits/stdc++.h>
#define LL long long
#define ULL unsigned long long
#define pb push_back
#define pii pair<int,int>
#define mk make_pair
#define endl "\n"
#define FIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define FIN freopen("1.txt","r",stdin)
#define all(x) x.begin(),x.end()
#define each(e,v) for(auto e: v)
#define debug(a,n) rep(i,0,n) cout<<a[i]<<" ";cout<<endl;
#define Time cout<<"Time="<<clock()-start_clock<<"ms"<<endl
#define mem(x,v) memset(x,v,sizeof(x))
#define repn(i,a,n) for(int i=a;i<=n;i++)
#define rep(i,a,n) for(int i=a;i<n;i++)
#define per(i,a,n) for(int i=n-1;i>=a;i--)
inline int reads(char s[]){char c;int len = 0;while ((c = getchar()) != ' ' && c!='\n') s[len++] = c;s[len] = 0;return len;}
char F[60];template<typename T> inline void write(T x) {if( x < 0 ) putchar( '-' ),x=-x;int cnt = 0 ;while(x) {F[cnt++] = x % 10 + '0' ;x /= 10 ;}while(cnt) putchar(F[--cnt]);putchar(10);}
template<typename T> inline void read(T &ret) {char c;ret = 0;T sgn = 1;do { c = getchar(); } while ((c < '0' || c > '9') && c != '-');if (c == '-') sgn = -1; else ret = c - '0';while ((c = getchar()) >= '0' && c <= '9') ret = ret * 10 + (c - '0'); ret*= sgn;}
template<typename T> inline void _max(T &a,const T b){if(a<b) a = b;}
template<typename T> inline void _min(T &a,const T b){if(a>b) a = b;}
template<typename T> inline void _add(T &a,const T b,const T MOD){a = (a+b)%MOD;}
template<typename T> inline T _mul(T a,T b,const T MOD){T ans = 0;while(b){if(b&1) _add(ans,a,MOD);_add(a,a,MOD);b>>=1;}return ans;}
template<typename T> inline T _pow(T a,T b,const T MOD){T ans = 1;while(b){if(b&1) ans = _mul(ans,a,MOD);a = _mul(a,a,MOD);b>>=1;}return ans;}
using namespace std;
const int N = 5010;
const int sigma_size = 255;
struct Node{
	int ch[sigma_size],len,fa;
}pool[N<<1];
int last = 1,tot = 1;
void extend(int x){
	int p = last;
	int np = last = ++tot;
	pool[np].len = pool[p].len + 1;
	for(;p&&!pool[p].ch[x];p = pool[p].fa) pool[p].ch[x] = np;
	if(!p) pool[np].fa = 1;
	else{
		int q = pool[p].ch[x];
		if(pool[q].len==pool[p].len	+1) pool[np].fa = q;
		else{
			int nq = ++tot;
			pool[nq] = pool[q];
			pool[nq].len = pool[p].len+1;
			pool[np].fa = pool[q].fa = nq;
			for(;p&&pool[p].ch[x]==q;p = pool[p].fa) pool[p].ch[x] = nq;
		} 
	}
}
char s1[N],s2[N];
int main(){
	#ifndef ONLINE_JUDGE
		FIN;
		int start_clock = clock();
	#endif
	char c;
	int len1 = reads(s1);
	int len2 = reads(s2);
	rep(i,0,len1) extend(s1[i]);
	string ans = "";
	int u = 1;string now = "";
	rep(i,0,len2){
		int p = s2[i];
		if(pool[u].ch[p]){
			now += s2[i];
			u = pool[u].ch[p];
			if(now.size()>ans.size()) ans = now;
			continue;
		}
		while(u&&!pool[u].ch[p]) u = pool[u].fa;
		if(!u){
			u = 1;now = "";
		}else{ 
			now = now.substr(now.size()-pool[u].len,pool[u].len);
			now += s2[i];
			u = pool[u].ch[p];
			if(now.size()>ans.size()) ans = now;
		}
	}
	if(ans.size()==0) cout<<-1<<endl;
	else cout<<ans<<endl;
	return 0;
} 

/*
题目要求额外空间复杂度O(1)，就不可以用动态规划了
可以将一个串不动，另一个串在此串上向后滑动，每滑动一格扫描一次重叠部分的最长公共子串
然后两个串互换，再滑一次。
最后取最长公共子串。
*/
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String str1 = scanner.nextLine();
        String str2 = scanner.nextLine();
        int size1 = str1.length();
        int size2 = str2.length();
        if (size1 == 0 || size2 == 0) {
            System.out.println("-1");
            return;
        }
        
        // 串2不动，串1向后滑动
        StringBuilder result = new StringBuilder();
        for (int i = 0; i < size2; ++i) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < size1 && i + j < size2; ++j) {
                if (str2.charAt(i + j) == str1.charAt(j)) {
                    sb.append(str1.charAt(j));
                } else {
                    result = result.length() > sb.length() ? result : sb;
                    sb = new StringBuilder();
                }
            }
            result = result.length() > sb.length() ? result : sb;
        }
        
        // 串1不动，串2向后滑动
        for (int i = 0; i < size1; ++i) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < size2 && i + j < size1; ++j) {
                if (str1.charAt(i + j) == str2.charAt(j)) {
                    sb.append(str2.charAt(j));
                } else {
                    result = result.length() > sb.length() ? result : sb;
                    sb = new StringBuilder();
                }
            }
            result = result.length() > sb.length() ? result : sb;
        }
        if (result.length() == 0) {
            System.out.println("-1");
            return;
        }
        System.out.println(result);
    }
}

C++ 代码 时间复杂度O(nm)，空间复杂度O(1)

因为计算每一个 的时候只需要计算，所以只要按照斜线方向（遍历 n + m - 1条斜线）计算所有的值，用一个变量维护最大值即可

核心：知道如何遍历 n + m - 1 条斜线（这里从最右上角的斜线开始）

C++ 代码

// 时间复杂度O(nm)，空间复杂度O(1)
#include <algorithm>
#include <iostream>

using namespace std;

int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    string a, b;
    cin >> a >> b;
    int n = a.size(), m = b.size();

    int len = 0, res = 0;
    int row = 0, col = m - 1; // 从右上角开始

    int lcs_i = 0, lcs_j = 0;

    // 计算矩阵中的每一条斜线上的值
    while (row < n) {
        int i = row, j = col; // 斜线起点
        while (i < n && j < m) { // 遍历当前斜线
            if (a[i] == b[j]) {
                len++;
                if (len > res) {
                    res = len;
                    lcs_i = i, lcs_j = j; // 记录最大长度子串的最后一个元素(i,j)
                }
            } else len = 0; // 断开后，len重新算
            i++, j++;
        }
        len = 0; // 下一条斜线 len 从 0 开始

        // 改变斜线起点
        if (col > 0) col--;
        else row++;
    }

    string s;
    row = lcs_i, col = lcs_j;
    while (row >= 0 && col >= 0) {
        if (a[row] == b[col]) s += a[row];
        else break;
        row--, col--;
    }

    reverse(s.begin(), s.end());

    if (res == 0)
        cout << -1 << endl;
    else
        cout << s << endl;

    return 0;
}

import sys

for line in sys.stdin:
    line = line.strip()
    if len(line)<=0:break

    line2 = input().strip()
    if len(line)>len(line2):
        long_str = line
        short_str = line2
    else:
        long_str = line2
        short_str = line
    m,n = len(long_str),len(short_str)
       
    max_len = 0
    max_res = ''
    flag = False
    for left in range(n):
        i,j = 0,left
        if flag:break
        while(i<m):
            if long_str[i]==short_str[j]:
                i+=1
                j+=1
                if j>=n:
                    if j-left+1>max_len:
                        max_len = n-left
                        max_res = short_str[left:]
                        flag = True
                    break
            else:
                if j-left+1>max_len:
                    max_len = j-left+1
                    max_res = short_str[left:j]
                j = left
                i+=1
    print(max_res)
            
        

    

先来一段暴力超时的代码，就是固定left然后往右遍历，去找最长的子串max_res，学到了更厉害的解法就来

import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str1 = sc.nextLine();
String str2 = sc.nextLine();
int m = str1.length();
int n = str2.length();
char[] ch1 = str1.toCharArray();
char[] ch2 = str2.toCharArray();
int[][] dp = new int[m + 1][n + 1];
for(int i = 0; i <= m; i++) {
dp[i][0] = 0;
}
for(int j = 0; j <= n; j++) {
dp[0][j] = 0;
}
//二维dp数组，动态规划
int max = 0;
int index = 0;
for(int i = 1; i <= m; i++) {
for(int j = 1; j <= n; j++) {
if(ch1[i - 1] == ch2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
}else {
dp[i][j] = 0;
}
if(dp[i][j] > max) {
index = i;
max = dp[i][j];
}
}
}
if(max == 0) {
System.out.println(-1);
}else {
String res = str1.substring(index - max, index);
System.out.println(res);
}
}
}

#include<bits/stdc++.h>
using namespace std;

int main(){
    string str1;
    string str2;
    cin>>str1;
    cin>>str2;
    int row = 0;
    int col = str2.size()-1;
    int max = 0;
    int end = 0;
    while(row < (int)str1.size()){
        int i = row;
        int j = col;
        int len = 0;
        while(i < (int)str1.size() && j < (int)str2.size()){
            if(str1[i]!=str2[j]){
                len = 0;
            }else{
                len++;
            }
            if(len > max){
                end = i;
                max = len;
            }
            i++;
            j++;
        }
        if(col > 0){
            col--;
        }else{
            row++;
        }
    }
    if (max == 0)
    {
        cout << -1;
        return 0;
    }else{
        for(int i = end-max+1;i < end+1; i++){
            cout<<str1[i];
        }
    }

return 0;

}

import java.util.HashSet;
import java.util.Objects;
import java.util.Scanner;
import java.util.Set;

public class TestZiChuan
{
 public static void main(String args[]){
  Scanner sc=new Scanner(System.in);
  String firstStr=sc.next();
  String secondStr=sc.next();
  Set<String> resultSet=new HashSet<String>();
  Set<String> resultFirst=getSonStr(firstStr);
  Set<String> secondFirst=getSonStr(secondStr);
  for(String result1:resultFirst){
   for(String result2:secondFirst){
    if(result1.equals(result2)){
     resultSet.add(result1);
    }
   }
  }
  
  String maxStr="";
  for(String result:resultSet){
   if(result.length()>maxStr.length()){
    maxStr=result;
   }
  }
  if(Objects.isNull(maxStr) || maxStr.equals("")){
   System.out.println("-1");
  }
  else{
   System.out.println(maxStr); 
  }
  sc.close();
 }
 
 public static Set<String> getSonStr(String input){
  Set<String> set=new HashSet<String>();
  int len=input.length();
  String tempStr;
  for(int i=0;i<len;i++){
   tempStr="";
   for(int j=i;j<len;j++){
    tempStr=tempStr+input.charAt(j);
    set.add(tempStr);
   }
  }
  return set;
 }
}