发个面试的题目，看看大家有好的解法没，有个大体的思路就好了。
给两个字符串，
例如：
a = "skmabcd12365 "
b = "suiskmabty365 "

找出他们两个公共最长的， 上面的就是 skmab 这个字符传。

[解决办法]
/* *******************************************************************
函数名称：commanString
函数功能：查找两个字符串的最大公共字串
函数参数：char * longString,char *shortString
返回值：char*
备注： 必须保证longString是比shortString长的字符串
******************************************************************** */
char* commanString(char *longString,char *shortString)
{
size_t llen=strlen(longString);
size_t slen=strlen(shortString);

if(strstr(longString,shortString)!=0)
return shortString;

char *subString=static_cast <char*> (malloc(slen));
for(size_t end=slen-1;end> 0;--end)
{
for(size_t begin=0;begin <slen-end;++begin)
{
memcpy(subString,&shortString[begin],end);
subString[end]= '\0 ';
if(strstr(longString,subString)!=0)
return subString;
}
}

return 0;
}
[解决办法]
KMP
[解决办法]
一个简单的办法
skmabcd12365
suiskmabty365
比较重叠部分得到最大相同.
然后移一位
skmabcd12365
suiskmabty365
一直做就可以了

skmabcd12365
suiskmabty365
这个时候得到最大串.

时间复杂度.
O(M*N)


[解决办法]
先顶一个
[解决办法]
那个复杂度又点高哦。。
[解决办法]
for(size_t begin=0;begin <slen-end;++begin)
{
memcpy(subString,&shortString[begin],end);
subString[end]= '\0 ';
if(strstr(longString,subString)!=0)
return subString;
}
---
这个不行，只能确定里面有 长字符串的字串，但无法确定是最长的。
[解决办法]
把字符串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 <stdio.h>
#include <stdlib.h>

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 != '\0 ' )
{
ptempBuffer1++;
str1Size++;
}
ptempBuffer2 = str2;
while( *ptempBuffer2 != '\0 ' )
{
ptempBuffer2++;
str2Size++;
}

ptempBuffer1 = ( char * ) malloc( str1Size );
pwork = ptempBuffer1;
memset( pwork, 0, str1Size );
ptempBuffer2 = ( char * ) malloc( str1Size );
plast = ptempBuffer2;
memset( plast, 0, str1Size );
for( i = 0; i < str2Size; i++ )
{
for( j = 0; j < str1Size; j++ )
{
if( *( str1 + j ) == *( str2 + i ) )
{

if( j == 0 )
{
*( pwork + j ) = 1;
}
else
{
*( pwork + j ) = *( plast + j - 1 ) + 1;
}
if( resultLength < *( pwork + j ) )
{
resultIndex = j;
resultLength = *( pwork + j );
}
}
else
{
*( pwork + j ) = 0;
}
}
ptemp = pwork;
pwork = plast;
plast = ptemp;
}
retstr = ( char * ) malloc( resultLength + 1 );
memcpy( retstr, str1 + resultIndex - resultLength + 1, resultLength );
*( retstr + resultLength ) = '\0 ';
printf( "resultIndex = %d, resultLength = %d\n ", resultIndex, resultLength );
free( ptempBuffer1 );
free( ptempBuffer2 );
return retstr;
}

int main(int argc, char *argv[])
{
char* ret = NULL;
ret = StringSearch( "adbccadebbca ", "edabccadece " );
printf( "result String is %s\n ", ret );
free( ret );
system( "PAUSE ");
return 0;
}

为了方便，采用了两个容量为m的一维数组来保存运行中的结果，空间复杂度为m+n+2*m（保存打印输出的结果字符串可以不需要），也就是O(m+n)。由于需要事先遍历字符串得到长度，算法复杂度为m*n + m + n，O(m*n)级别。


[解决办法]
帮顶了，这个题很经典...
[解决办法]
跟最大子序列和的问题类似。可以理解为“a中最长子序列（跟b相同的子串）”问题。

最大子序列问题可以用线性时间复杂度O(n)解决。这个也可以。
[解决办法]
具体可以搜一下“最大子序列和”的线性算法。
[解决办法]
跟最大子序列和的问题类似。可以理解为“a中最长子序列（跟b相同的子串）”问题。

最大子序列问题可以用线性时间复杂度O(n)解决。这个也可以。

想不出来O(n)的解法.
[解决办法]
O(n)难实现！