最长公共子串问题：
给定两个字符串A和B，求解两个字符串的最长公共子串。子串必须连续。
如:A :" abcdef"；B："cdefgh"。最长公共子串为"cdef"，返回为4。
问题分析过程可以参考最长公共子序列。http://www.cnblogs.com/gaobaoru-articles/p/5450576.html
程序实现：
1 /*************************************** 2 FileName LongestCommonSubstring.cpp 3 Author : godfrey 4 CreatedTime : 2016/5/7 5 ****************************************/ 6 #include <iostream> 7 #include <cstring> 8 #include <vector> 9 #include <algorithm> 10 #include <stdio.h> 11 #include <stdlib.h> 12 13 using namespace std; 14 15 int LongestCommonSubstring(char* str1,char* str2){ 16 int32_t MaxLength = 0; 17 int32_t len1 = strlen(str1); 18 int32_t len2 = strlen(str2); 19 int32_t chess[len1+1][len2+1]; 20 for(int i=0;i < len1;i++){ 21 if(str1[i] == str2[0]){ 22 chess[i][0] = 1; 23 MaxLength = 1; 24 } 25 else{ 26 chess[i][0] = 0; 27 } 28 } 29 for(int j=0;j<len2;j++){ 30 if(str2[j] == str1[0]){ 31 chess[0][j] = 1; 32 MaxLength = 1; 33 } 34 else{ 35 chess[0][j] = 0; 36 } 37 } 38 for(int i = 1;i<len1;i++){ 39 for(int j=1;j<len2;j++){ 40 if(str1[i] == str2[j]){ 41 chess[i][j] = chess[i - 1][j - 1] + 1; 42 if(MaxLength < chess[i][j]) 43 MaxLength = chess[i][j]; 44 } 45 else{ 46 chess[i][j] = 0; 47 } 48 } 49 } 50 return MaxLength; 51 } 52 int main() 53 { 54 char str1[1024],str2[1024]; 55 int32_t num; 56 while(scanf("%s%s",str1,str2) != EOF){ 57 num = LongestCommonSubstring(str1,str2); 58 printf("The longest Common Substring is: %d ",num); 59 } 60 return 0; 61 }
运行结果：
转载请注明出处：
C++博客园：godfrey_88