求两字符串最长公共连续子串---C++编程

旧城等待， 2022-06-15 06:57 184阅读 0赞

**题目：有两个字符串（可能包含空格）,找出其中最长的公共连续子串，并输出其长度。 **

##### 输入描述：输入为两行字符串（可能包含空格），长度均小于等于50。 #####

##### 输出描述:  输出为一个整数，表示最长公共连续子串的长度。 #####

##### 输入例子: #####

##### abcde #####

##### abgde #####

##### 输出例子: #####

##### 2 #####

### 两种参考思路如下：   （1）假设两个字符串str1和str2的长度分别为m和n，构建一个矩阵（即二维数组）M\[m\]\[n\]，初始值都设为0，如果字符串str1中 ###

### 第i个字符str\[i-1\](下标从零开始)与字符串str2中第j个字符串str\[j-1\]相等，则将matric\[i\]\[j\]设为1。最后统计矩阵M中对角线最大的连续1的个数， ###

### 即为两字符串最长公共子串。注：如不好理解，可以画图辅助。 ###

`/*例如：str1: abcde    str2: abgde  `

`               ` `matrix = [ 1  0  0  0  0 `

`                 ` `0  1  0  0  0`

`                 ` `0  0  0  0  0`

`                 ` `0  0  0  1  0`

`                 ` `0  0  0  0  1 ]`

`   ` `斜线上连续的1的最大个数为2，所以最长公共连续子串长度为2*/ 是每条对角线，而不只是主对角线。`

参考代码如下：

\#include <iostream>  
\#include <string>  
using namespace std;  
int main()  
  \{  
      char str1\[51\],str2\[51\];  
      int matric\[51\]\[51\]=\{0\};         
      int  MaxLen=0;  
      gets(str1);   //cin.getline(str1,51);  
      gets(str2);  
      for(int i=0;str1\[i\]!='\\0';i++)      //如果两个位置的元素相等，矩阵值为1  
        \{  
           for(int j=0;str2\[j\]!='\\0';j++)  
              \{  
                 if(str1\[i\]==str2\[j\])  
                     matric\[i\]\[j\]=1;  
              \}  
        \}        
      for(int i=0;str1\[i\]!='\\0';i++)      //依次找对角线最大连续1的个数  
        \{  
           for(int j=0;str2\[j\]!='\\0';j++)  
              \{  
                 int m=i;  
                 int n=j;  
                 int len=0;  
                 while(matric\[m++\]\[n++\]==1)  
                     len++;  
                 if(MaxLen<len)  
                     MaxLen=len;  
              \}  
       \}  
     cout<<MaxLen<<endl;  
  \}

（2）运用动态规划的思想。

解题思路：

这题其实是动态规划的变形经典题型，应用动态规划的思想，创建一个二维数组dp\[n\]\[n\]，其中dp\[i\]\[j\]，表示取到s1\[i\]和取到s2\[j\]时的最大连续子串长度。如果s1\[i\]等于s2\[j\]，则dp\[i-1\]\[j-1\]等于取到s1\[i-1\]和取到s2\[j-1\]时的最大连续子串长度加1，即

dp\[i\]\[j\]=dp\[i-1\]\[j-1\]+1。

`#include <stdio.h>`

`#include <string.h>`

`#define N 50`

`int` `main(){`

`    ` `char` `s1[N],s2[N];`

`    ` `int` `dp[N][N],i,j,max_len=0;`

`    ` `gets` `(s1);`

`    ` `gets` `(s2);`

`    ` `for` `(i=0;i<` `strlen` `(s1);i++){`

`        ` `for` `(j=0;j<` `strlen` `(s2);j++){`

`            ` `if` `(s1[i]==s2[j]){`