求最长公共子串（串）

求最长公共子串（串）

时间： 1ms        内存：128M

描述：

求采用顺序结构存储的串s和串t的一个最长公共子串，若没有则输出false，若最长的有多个则输出最先出现的那一串。

输入：

输入两个字符串

输出：

输出公共子串

示例输入：

abcdef
adbcef

示例输出：

bc

提示：

参考答案（内存最优[752]）：

#include<stdio.h>
#include<string.h> 
typedef unsigned char string[200];
int substring(string sub,string s,int pos,int leng)
{
	int len=strlen(s);
	if(pos<0||pos>len||leng<0||leng+pos>len)
		return 0;
	else{
		int i;
		for(i=0;i<leng;i++)
			sub[i]=s[pos+i];
		sub[i]=0;
		return 1;
	}
}
int main()
{
	string s,t,ssub,tsub,sub;
	unsigned int leng,i,j,len=0;
	gets(s);
	gets(t);
	for(leng=1;s[leng-1]!=0&&t[leng-1]!=0;leng++){
		for(i=0;s[i+leng-1]!=0;i++){
			if(substring(ssub,s,i,leng))
			for(j=0;t[j+leng-1]!=0;j++){
				if(substring(tsub,t,j,leng))
					if(strcmp(ssub,tsub)==0&&len<strlen(ssub)){
						strcpy(sub,ssub);
						len=strlen(sub);
					}
			}
		}
	}
	printf("%s",sub);
	return 0;
}

参考答案（时间最优[0]）：

#include<stdio.h>
#include<string.h> 
typedef unsigned char string[200];
int substring(string sub,string s,int pos,int leng)
{
	int len=strlen(s);
	if(pos<0||pos>len||leng<0||leng+pos>len)
		return 0;
	else{
		int i;
		for(i=0;i<leng;i++)
			sub[i]=s[pos+i];
		sub[i]=0;
		return 1;
	}
}
int main()
{
	string s,t,ssub,tsub,sub;
	unsigned int leng,i,j,len=0;
	gets(s);
	gets(t);
	for(leng=1;s[leng-1]!=0&&t[leng-1]!=0;leng++){
		for(i=0;s[i+leng-1]!=0;i++){
			if(substring(ssub,s,i,leng))
			for(j=0;t[j+leng-1]!=0;j++){
				if(substring(tsub,t,j,leng))
					if(strcmp(ssub,tsub)==0&&len<strlen(ssub)){
						strcpy(sub,ssub);
						len=strlen(sub);
					}
			}
		}
	}
	printf("%s",sub);
	return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。