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

 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 }