在解读本文之前，建议先了解“动态规划方法论”，相关内容可以在之前的文章中找到。

本文将讲解与LeetCode718.最长重复子数组相同的题目，阅读完本文后可以尝试挑战这道题。

力扣链接

题目叙述：

给定两个字符串，输出它们最长公共子串的长度。

输入

ABACCB
AACCAB

输出

3

解释

最长公共子串是ACC，其长度为3。

与最长公共子序列的区别

• 公共子串：字符必须是连续相等的
• 公共子序列：字符必须是相等的，可以不连续。

动态规划思路

• 只有当两个字符串中的字符连续相等时，公共子串的长度才会不断增加，否则清零。
• 因此，公共子串问题实际上是公共子序列问题的一个特殊情况。

状态变量以及其含义

• 延续“最长公共子序列”的思路，可以使用两个指针变量 i 和 j 来遍历字符串a和b。
• 因此， f[i][j] 代表着以 a[i] 和 b[j] 为结尾的公共子串的长度。

递推公式

• 递推公式如下：
• f[i][j]=f[i-1][j-1]+1 （ a[i]==b[j] ）
• f[i][j]=0 （ a[i]!=b[j] ）
• 边界条件为：
• f[0][j]=0
• f[i][0]=0

遍历顺序：

• 从上到下，从左到右。

如何初始化？

• 处理好上述边界条件，并根据递推公式进行初始化 f 数组。

举例打印dp数组

• 举例如下图所示：

• f[i][j] 的值如图所示。

最终代码实现

#include
#include
using namespace std;

char a[200]="BCCABCCB";
char b[200]="AACCAB";
int f[201][201];

int main(){
  int ans=0;
  for(int i=1; i<=strlen(a); i++){
    for(int j=1; j<=strlen(b); j++){
      if(a[i-1]==b[j-1]) f[i][j]=f[i-1][j-1]+1;
      ans=max(ans,f[i][j]);
    }
  }
  printf("ans=%d\n",ans);
  return 0;
}