2011年3月11日 onedouble.net
今天在面试翻倒一个问题：求两个字符串的最大公共子串，我用逐个B的越来越短的子串去A中FIND，总觉得效率不高，搜索了一下有一个算法很巧妙：
把字符串1（长度m）横排，串2（长度n）竖排，得到一个m×n的矩阵c，矩阵的每个元素的值如下，如果m[i]=n[j]，则c[j][i]=1,否则，c[j][i]=0。然后找出矩阵中连续是1的对角线最长的一个，则对角线的长度就是公共子串的长度.
经过改进，可以不需要构造矩阵，因为第i行如果有字母匹配，其取值仅与第i-1行相关，若m[i]=n[j]，则c[j][i] = c[j-1][i-1] + 1，这样仅需要记录一个长度为m的一维数组就可以了。
鼓捣出来的代码如下：
1 #include <stdio.h>
2 #include <stdlib.h>
3
4 char * StringSearch( char * str1, char * str2 )
5 {
6 int i;
7 int j;
8 char* ptempBuffer1;
9 char* ptempBuffer2;
10 char* pwork;
11 char* plast;
12 char* ptemp;
13 char* retstr;
14 int resultIndex = 0;
15 int resultLength = 0;
16 int str1Size = 0;
17 int str2Size = 0;
18 ptempBuffer1 = str1;
19 while( *ptempBuffer1 != '\0' )
20 {
21 ptempBuffer1++;
22 str1Size++;
23 }
24 ptempBuffer2 = str2;
25 while( *ptempBuffer2 != '\0' )
26 {
27 ptempBuffer2++;
28 str2Size++;
29 }
30
31 ptempBuffer1 = ( char * ) malloc( str1Size );
32 pwork = ptempBuffer1;
33 memset( pwork, 0, str1Size );
34 ptempBuffer2 = ( char * ) malloc( str1Size );
35 plast = ptempBuffer2;
36 memset( plast, 0, str1Size );
37 for( i = 0; i < str2Size; i++ )
38 {
39 for( j = 0; j < str1Size; j++ )
40 {
41 if( *( str1 + j ) == *( str2 + i ) )
42 {
43 if( j == 0 )
44 {
45 *( pwork + j ) = 1;
46 }
47 else
48 {
49 *( pwork + j ) = *( plast + j - 1 ) + 1;
50 }
51 if( resultLength < *( pwork + j ) )
52 {
53 resultIndex = j;
54 resultLength = *( pwork + j );
55 }
56 }
57 else
58 {
59 *( pwork + j ) = 0;
60 }
61 }
62 ptemp = pwork;
63 pwork = plast;
64 plast = ptemp;
65 }
66 retstr = ( char * ) malloc( resultLength + 1 );
67 memcpy( retstr, str1 + resultIndex - resultLength + 1, resultLength );
68 *( retstr + resultLength ) = '\0';
69 printf( "resultIndex = %d, resultLength = %d\n", resultIndex, resultLength );
70 free( ptempBuffer1 );
71 free( ptempBuffer2 );
72 return retstr;
73 }
74
75 int main(int argc, char *argv[])
76 {
77 char* ret = NULL;
78 ret = StringSearch( "adbccadebbca", "edabccadece" );
79 printf( "result String is %s\n", ret );
80 free( ret );
81 system("PAUSE");
82 return 0;
83 }
为了方便，采用了两个容量为m的一维数组来保存运行中的结果，空间复杂度为m+n+2*m（保存打印输出的结果字符串可以不需要），也就是O(m+n)。由于需要事先遍历字符串得到长度，算法复杂度为m*n + m + n，