[编程题] 最长公共连续子串
时间限制：1秒
空间限制：32768K
牛牛有两个字符串（可能包含空格）,牛牛想找出其中最长的公共连续子串,希望你能帮助他,并输出其长度。
输入描述:
输入为两行字符串（可能包含空格），长度均小于等于50.
输出描述:
输出为一个整数，表示最长公共连续子串的长度。
输入例子:
abcde abgde
输出例子:
2
自己的解题思路：针对两个字符串，定义函数GetEqualCount来求得对于字符串long从L_start开始与字符串short比较得到的最长公共连续子串的长度
然后对于两个字符串，先对于a从0-length1位分别与b[0]对应求出最长公共连续子串的长度
例 abcde abc
abcde
abc
abcde
abc
abcde
abc
abcde
abc
abcde
abc
再对于b从0-length2分别与a[0]对应比一遍
abc
abcde
abc
abcde
abc
abcde
此时所有情况遍历到，max_count为所求，输出即可
1 #include <iostream> 2 using namespace std; 3 4 int GetEqualCount(string L,string S,int L_start,int L_len,int S_Len) 5 { 6 int count = 0; 7 int max_count = 0; 8 int j = 0; 9 for(int i = L_start;i<L_len;i++) 10 { 11 if(j == S_Len) 12 { 13 max_count = max(max_count,count); 14 count=0; 15 break; 16 } 17 if(L[i] == S[j]) 18 { 19 count++; 20 j++; 21 } 22 else 23 { 24 max_count = max(max_count,count); 25 count=0; 26 j++; 27 } 28 } 29 max_count = max(max_count,count); 30 return max_count; 31 32 } 33 int main() 34 { 35 string a; 36 string b; 37 getline(cin,a); 38 getline(cin,b); 39 40 int length1 = a.size(); 41 int length2 = b.size(); 42 43 int count = 0; 44 int max_count = 0; 45 46 for(int i=0;i<length1;i++) 47 { 48 count = GetEqualCount(a,b,i,length1,length2); 49 max_count = max(max_count,count); 50 } 51 for(int i=0;i<length2;i++) 52 { 53 count = GetEqualCount(b,a,i,length2,length1); 54 max_count = max(max_count,count); 55 } 56 57 cout<<max_count<<endl; 58 59 return 0; 60 }
参考网上，用空间换时间解题思路：
假设两个字符串str1和str2，长度分别为m和n，则构建一个m*n的矩阵matrix，
matrix[i][j]==1表示字符串str1中第i个字符与str2中第j个字符相等，为0则不相等。
统计矩阵matrix中每条斜线上1的连续最大个数就是str1和str2中公共连续子串的最大长度
例如：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
假设两个字符串str1和str2，长度分别为m和n，则构建一个m*n的矩阵matrix，
matrix[i][j]==1表示字符串str1中第i个字符与str2中第j个字符相等，为0则不相等。
统计矩阵matrix中每条斜线上1的连续最大个数就是str1和str2中公共连续子串的最大长度
例如：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
1 #include <iostream> 2 using namespace std; 3 int main() 4 { 5 char str1[51]; 6 char str2[51]; 7 int leng, maxleng=0; 8 cin.getline(str1,51); 9 cin.getline(str2,51); 10 int matrix[50][50] = {0};//构建初始矩阵matrix 11 for(int i = 0;str1[i] != ' ';i++) 12 { 13 for(int j = 0; str2[j] != ' '; j++) 14 { 15 if(str1[i] == str2[j]) 16 matrix[i][j] = 1;//如果str1中第i个字符与str2中第j个字符相等，则为1 17 } 18 } 19 //循环统计每条斜线上的连续1的个数 20 for(int i = 0;str1[i] != ' ';i++) 21 { 22 for(int j = 0; str2[j]!= ' '; j++) 23 { 24 leng = 0; 25 int m = i; 26 int n = j; 27 while(matrix[m++][n++] == 1)//判断其右下角位置是否为1 28 leng++; 29 if(maxleng < leng) 30 maxleng = leng; 31 } 32 } 33 cout << maxleng; 34 return 0; 35 }