动态规划

状态转移方程：f[i][j] = f[i - 1][j - 1] + 1
f[i][j]表示以a[i]和b[j]结尾的最长公共子串的长度

#include<iostream>
#include<string>

using namespace std;

const int N = 1010;
char a[N], b[N];
int f[N][N];    // f[i][j]表示以a[i]和b[j]结尾的最长公共子串的长度

int main() {

    scanf("%s%s", a + 1, b + 1);
    string str1(a + 1);
    int n = str1.length();  // 获取数组a的长度
    string str2(b + 1);
    int m = str2.length();  // 获取数组b的长度

    int res = 0;    // 记录最长子串的长度
    int endIndex = 1;   // 记录最长子串在数组a中的结束位置
    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= m ; j ++) {
            if (a[i] == b[j]) {     // 如果a[i]和b[j]相等就更新res
                f[i][j] = f[i - 1][j - 1] + 1;
                if (res < f[i][j]) {
                    endIndex = i;
                    res = f[i][j];
                }

            }
            else {
                f[i][j] = 0;
            }
        }
    }

    if (res == 0) cout << "NULL" << endl;
    else for (int i = endIndex + 1 - res; i <= endIndex; i ++) cout << a[i];

    return 0;
}