華星筆試題目

求兩個字串的最大公共子串

把字串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 != '