给定两个字符串A和B，长度分别为m和n，要求找出它们最长的公共子串，并返回其长度。例如：
A = "HelloWorld" B = "loop"
子序列和子串都是字符集合的子集，但是子序列不一定连续，但是子串一定是连续的。
dp[i][j]：以A中第i个字符结尾的子串和B中第j个字符结尾的子串的的最大公共子串的长度。
dp 的大小也为 (n + 1) x (m + 1) ，多出来的一行和一列是第 0 行和第 0 列，初始化为 0，表示空字符串和另一字符串的子串的最长公共子串。
我们先判断A的第i个元素和B的第j个元素是否相同，即判断A[i - 1]和 B[j -1]是否相同，如果相同它就是dp[i - 1][j- 1] + 1，相当于在两个字符串都去掉一个字符时的最长公共子串再加 1；否则最长公共子串取0。
相应的状态转移方程为：
AC代码
#include<iostream> #include<cstring> #include<algorithm> using namespace std; const int N = 1005; char s1[N]; char s2[N]; int dp[N][N]; int main() { cin >> s1 >> s2; int l1 = strlen(s1); int l2 = strlen(s2); int ans = 0; memset(dp, 0, sizeof(dp)); for (int i = 1; i <= l1; i++) { for (int j = 1; j <= l2; j++) { if (s1[i - 1] == s2[j - 1]) { dp[i][j] = dp[i - 1][j - 1] + 1; ans = max(ans, dp[i][j]); } } } cout << ans << endl; return 0; }
原文：https://www.cnblogs.com/yun-an/p/11380667.html