求兩個字符串的最大公共子串
把字符串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的一維數組就可以了。
鼓搗出來的代碼如下:
#include
#include
char * StringSearch( char * str1, char * str2 )
{
int i;
int j;
char* ptempBuffer1;
char* ptempBuffer2;
char* pwork;
char* plast;
char* ptemp;
char* retstr;
int resultIndex = 0;
int resultLength = 0;
int str1Size = 0;
int str2Size = 0;
ptempBuffer1 = str1;
while( *ptempBuffer1 != '