线性dp：最长公共子串
最长公共子串[*]本文讲解的题与leetcode718.最长重复子数组，题意千篇一律，阅读完本文以后可以去挑衅这题。
力扣链接
题目叙述：
给定两个字符串，输出其最长公共子串的长度。
输入
ABACCB
AACCAB输出
3解释
最长公共子串是ACC，其长度为3。
与最长公共子序列的区别
[*]公共子串：字符必须是连续相称的
[*]公共子序列：字符必须是相称的，可以不连续。
动态规划思路
[*]只有当两个字符串中的字符连续相称的时候，公共子串的长度才不断增长，否则清零
[*]因此，我们不难发现，公共子串题目其实是公共子序列题目的一个特殊情况
状态变量以及其含义
[*]我们延续最长公共子序列的思路，可以利用两个指针变量，i和j来遍历a，b字符串。
[*]那么我们的f代表着什么呢？因为本题是要连续的子串，因此我们的 f表示以a和b为末端的公共子串的长度
递推公式
[*]那么，我们很容易的就可以得出递推公式：
[*]f=f+1（a==b）
[*]f=0）（a!=b）
[*]边界条件为：
[*]f=0
[*]f=0
遍历顺序：
[*]显然是从上到下，从左到右。
怎样初始化？
[*]处理好上面所说的边界条件，并且根据递推公式来进行初始化f数组即可。
举例打印dp数组
[*]举例如如图所示：
https://img2024.cnblogs.com/blog/3476421/202408/3476421-20240819180851101-1870799186.png
[*]f 的值如图所示。
最终代码实现
#include#includeusing namespace std;char a="BCCABCCB";char b="AACCAB";int f;int main(){int ans=0;for(int i=1; i
页:
[1]