蓝桥杯--最长公共字串

题目描述：
最大公共子串长度问题就是：
求两个串的所有子串中能够匹配上的最大长度是多少。
比如："abcdkkk" 和 "baabcdadabc"，
可以找到的最长的公共子串是"abcd",所以最大公共子串长度为4。
下面的程序是采用矩阵法进行求解的，这对串的规模不大的情况还是比较有效的解法。
题目解析：

求最长公共子串与最长公共子序列不一样，字串要求字符之间要连续，而子序列之间可以不连续，只要满足相对位置一样就行。

求最长公共字串，最直接、最简单的方式就是暴力求解，两层for循环，记录能匹配的最大字串长度即可。

但是，人总是要在追逐卓越的路上更进一步，所以不能满足于这种简单的解题方法。

最长公共字串与最长公共子序列方法差别多，动态规划的思想，a[i][j]表示到字符串s1的i位置和s2的j位置的最大公共子串的长度 ，数组初始化为0。为了方便理解，我们这么想，如果s1的字符串的第一个字符和s2的第一个字符相同，那么a[1][1] = 1;如果两个字符串的第二个字符和相同，那么，到第二个位置的最长公共子串就等于1+1 = 2，也就是到第一个字符的公共子串的个数+1。即a[i][j] = 1+ a[i-1][j-1]。因此，我们可以从第一个位置开始递推求出到任意一个位置的公共子串，在递推过程中记录最大的结果即可。
代码如下：

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
using namespace std;
int dp(char * s1,char * s2){
 　　int len1 = strlen(s1);
 　　int len2 = strlen(s2);
　　 int data[len1+1][len2+1];
 　　memset(data,0,sizeof(int)*(len1+1)*(len2+1));
 　　int max = 0;
 　　for(int i = 1;i <= len1;i++){
  　　　　for(int j = 1;j <= len2;j++){
   　　　　　　if(s1[i-1] == s2[j-1]){
    　　　　　　data[i][j] = data[i-1][j-1] + 1;
   　　　　　　 if(max < data[i][j])
    　　　　　　　　 max = data[i][j];
   　　　　　　}
 　　　　 }
 　　}
 　　return max;
}
int main(void){
 　　cout << dp("abcdekkk","baabcdeadabc") << endl;
 　　return 0;
}

蓝桥杯--最长公共字串

原文：https://www.cnblogs.com/Alice-Fourier/p/12380804.html