求两个字符串的最大公共字串

2014-11-23 22:08:42 · 作者: · 浏览: 4
//今天面试遇到一个有趣的题目 取两个字符串的最大公共字符串
//解决方案如下:

#include 
#include 
#include 

//先造一个常用函数
char* strsub( char const* pStrSrc, int iStart, int iLen )
{
	if( !pStrSrc || iStart <  0 )
		return NULL;

	int iStrLen = strlen( pStrSrc );

	char* pStrRes = NULL;
	if( iLen >= iStrLen - iStart )
	{
		pStrRes = (char*)malloc( iStrLen - iStart + 1 );

		if( !pStrRes )
			return NULL;

		memset( pStrRes, 0,  iStrLen - iStart + 1 );

		strncpy( pStrRes, pStrSrc + iStart, iStrLen  - iStart );

		return pStrRes;
	}
	else
	{
		pStrRes = (char*)malloc( iLen + 1 );
		
		if( !pStrRes )
			return NULL;

		memset( pStrRes, 0, iLen + 1 );

		strncpy( pStrRes, pStrSrc + iStart, iLen );

		return pStrRes;

	}

}

char* maxComm( char* pStrLeft, char* pStrRight )
{
	if( !pStrLeft || !pStrRight )
	{
		return NULL;
	}

	char* pStrLess = NULL;
	char* pStrMore = NULL;
	char* pStrRes= NULL;

	int iLeft = strlen( pStrLeft );
	int iRight = strlen( pStrRight );

	int iLess = ( iLeft <= iRight )   iLeft : iRight;

	int i,j;
	
	if( iLeft <= iRight )
	{
		pStrLess = pStrLeft;
		pStrMore = pStrRight;
	}
	else
	{
		pStrLess = pStrRight;
		pStrMore = pStrLeft;
	}
	char* pSt = NULL;

	for( i = iLess; i >
0; i-- ) { for( j = 0; j <= iLess - i; j++ ) { pStrRes = strsub( pStrLess, j, i ); if( strstr( pStrMore, pStrRes ) ) return pStrRes; free( pStrRes ); pStrRes = NULL; } } return NULL; } int main( int argc, char** argv ) { char* pStrLeft = "adasdfabc"; char* pStrRight = "asdabcasdf"; puts( "max comm string between two strings" ); char* strMaxComm = maxComm( pStrLeft, pStrRight ); printf( strMaxComm ); puts( "" ); free( strMaxComm ); strMaxComm = NULL; return 0; }