求两个字符串最长公共子串的问题 LCS

[c]代码库

#include<stdio.h>
#include<string.h>
#define N 100

//LCS问题就是求两个字符串最长公共子串的问题
char *LCS ( char *a,char *b )
{
	int len_a = strlen ( a );  //获取字串的长度
	int len_b = strlen ( b );
	char *p;
	int c[N][N] = {0};      //矩阵c记录两串的匹配情况
	int start,end,len,i,j;  //start表明最长公共子串的起始点，end表明最长公共子串的终止点
	end = len = 0;          //len表明最长公共子串的长度
	for ( i=0; i<len_a; i++ )    //串开始从前向后比较
	{
		for ( j=0; j<len_b; j++ )
		{
			if ( a[i] == b[j] )
				if ( i == 0 || j == 0 )
					c[i][j] = 1;
				else
					c[i][j] = c[i-1][j-1] + 1;
			//	else
			//		c[i][j] = 0;
			if ( c[i][j] > len )
			{
				len = c[i][j];
				end = j;
			}
		}
	}
	start = end - len + 1;
	p = ( char * ) malloc ( len+1 ); //数组p记录最长公共子串
	for ( i=start; i<=end; i++ )
		p[i-start] = b[i];
	p[len] = '\0';
	for ( j=0; j<len_b; j++ )
	{
		for ( i=0; i<len_a; i++ )
			printf ( "%2d",c[i][j] );
		printf ( "\n" );
	}
	return p;
}
int main ( int argc,char *argv[] )
{
	char str1[N],str2[N];
	printf ( "请输入字符串1：" );
	gets ( str1 );
	printf ( "请输入字符串2：" );
	gets ( str2 );
	printf ( "最长子串为：%s\n",LCS ( str1,str2 ) );
	return 0;
}