<span>最长公共子串</span>

最长公共子串问题:

给定两个字符串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\n",num);
59     }
60     return 0;
61 }

运行结果:

转载请注明出处:

C++博客园:godfrey_88

http://www.cnblogs.com/gaobaoru-articles/

 

全部评论

相关推荐

粗心的雪碧不放弃:纯学历问题,我这几个月也是一直优化自己的简历,后来发现优化到我自己都觉得牛逼的时候,发现面试数量也没有提升,真就纯学历问题
点赞 评论 收藏
分享
头像
10-16 09:58
已编辑
门头沟学院 Java
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务