首页 > 代码库 > 寻找最长公共子串的问题

寻找最长公共子串的问题

问题:现在有两个字符串,我们要寻找它们最长的公共子串。比如regression和express这两个字符串,它们的子串有e和ress,那么它们的最长公共字串就是ress。

 

解法:

我们利用一个二维数组来记录两个字符串相互匹配的情况,如果字符串str1长度为len1,字符串str2长度为len2,那么数组可以设为table[len1][len2]。

对于数组中的每个元素table[i][j],当字符串对应位置的值一致时(str1[i] == str2[j])为1,不一致时为0。当全部对比完成之后,数组中对角线上连续出现1的次数最多的,就是它们的连续的最长公共子串的长度。

但是由于我们要找的是它们最长公共字串的值,并且要找到对角线上连续出现1的次数也需要新的计算。我们可以改进算法:当字符串对应位置的值一致时(str1[i] == str2[j]),table[i][j] = table[i-1][j-1] + 1。这样,我们就可以方便地得到最长公共子串的长度了。同时我们可以记录table[i][j]最大时,i或者j的序号,就可以得到最长公共子串的位置了。

 

代码如下:

 1 void lcs(char* str1, char* str2) 2 { 3     // get length of the strings 4     int len1 = strlen(str1); 5     int len2 = strlen(str2); 6     // build 2-D array 7     vector<vector<int> > arr; 8     arr.resize(len1); 9     for(int i = 0; i < len1; i++) {10         arr[i].resize(len2);11     }12     // compare13     int maxLen = 0;14     int maxIdx = 0;15     int i;16     int j;17     i = 0;18     for (j = 0; j < len2; j++) {19         if (str2[j] == str1[i]) {20             arr[i][j] = 1;21         }22     }23     j = 0;24     for (i = 0; i < len1; i++) {25         if (str2[j] == str1[i]) {26             arr[i][j] = 1;27         }28     }29     for (i = 1; i < len1; i++) {30         for (j = 1; j < len2; j++) {31             if (str2[j] == str1[i]) {32                 arr[i][j] = arr[i-1][j-1] + 1;33                 if (arr[i][j] > maxLen) {34                     maxLen = arr[i][j];35                     maxIdx = i;36                 }37             }38         }39     }40     // output lcs41     char *result = (char *) malloc(maxLen+1);42     memcpy(result, str1 + maxIdx - maxLen + 1, maxLen);43     result[maxLen] = \0;44     printf("str1:%s\n", str1);45     printf("str2:%s\n", str2);46     printf("result:%s\n", result);47 }

 

寻找最长公共子串的问题