主题：第41次编程比赛之主打题
BigCarrot [专家分：10] 发布于 2006-09-14 21:43:00
求两个字符串的最长公共子串的长度
若有字符串s1,s2,cs, 其中cs既是s1的子串也是s2的子串, 则cs被称作为s1和s2的公共子串，比如
s1 = "abcdefg"
s2 = "xadzfcy"
则"adf"是s1和s2的公共子串，"ac"是另外一个公共子串, "adfc"则不是公共子串
假设一个公共子串cs的长度为len, 并且我们找不到长度大于len的公共子串, 那么cs可以被称为是s1和s2的最长公共子串, len就是最长公共子串的长度. 上例中, s1和s2的最长公共子串为"adf", 最长公共子串的长度为3
注意两个字符串的最长公共子串有可能有多个,
s1 = "ab"
s2 = "ba"
字符串"a" 和"b"都是s1和s2的最长公共子串,但是最长公共子串的长度只有一个, 就是1
请编写程序求给定两个字符串的最长公共子串的长度, 函数原型为
int LCS(char* str1, char* str2);
测试环境
P3M 1.2G 640MB
visual studio 2002, release mode
运行时间为10s, 字符串长度最长20000, 如果大家程序都比较快,我会继续增加字符串的长度
本次比赛截止时间为星期六下午一点整，到时间后我会另开一贴供大家提交自己的测试数据, 到星期天晚上七点截止. 这些数据和我自己的数据都会被用来测试大家提交的程序.
回复列表 （共14个回复）
11 楼
kirby1985 [专家分：0] 发布于 2006-09-16 11:49:00
int LCS(char *str1,char *str2)
{
char s1[20000],c2[20000],*cp1,*cp2,*cp;
cp1=s1;cp2=s2;
int k=0,t=0,max;
for(;*str1!='\0';str1++)
for(;*str2!='\0';str2++)
{if(*str1==*str2)
{*cp1=*str1;cp1++;k++;}
else
continue;
}
*cp1='\0';
for(;*str2!='\0';str2++)
for(;*str1!='\0';str1++)
{if(*str1==*str2)
{*cp2=*str1;cp2++;t++;}
else
continue;
}
*cp2='\0';
if(k>t)
{cp=s1;max=k;}
else
{cp=s2;max=t;}
printf("这两个字符串的最长公共子串是：");
puts(*cp);
printf("其长度是%d",max);
}
12 楼
boxertony [专家分：23030] 发布于 2006-09-16 12:49:00
int LCS(char *x, char *y)
{
int max = 0;
int lenx = strlen(x);
int leny = strlen(y);
int i, j;
int *z;
char *p1, *p2;
int len1, len2;
if(lenx >= leny)
{
len1 = lenx;
len2 = leny;
p1 = x;
p2 = y;
}
else
{
len1 = leny;
len2 = lenx;
p1 = y;
p2 = x;
}
z = new int[len2+1];
assert(z != NULL);
z[0] = 0;
int last, temp;
for(i=1; i<=len1; ++i)
{
last = z[0];
for(j=1; j<=len2; ++j)
{
if(p1[i-1] == p2[j-1])
{
temp = z[j];
z[j] = last + 1;
last = temp;
if(z[j] > max)
max = z[j];
}
else
{
last = z[j];
z[j] = 0;
}
}
}
delete []z;
return max;
}
// 另一个更快的算法来不及调试通过了。
13 楼
sllone [专家分：150] 发布于 2006-09-16 16:56:00
//用c++做的,提交格式不对的请包涵
//复杂度小于O(n`2)吧
#include<iostream>
#include<vector>
#include<cassert>
#define LEN 100
int LCS(char *s1,char *s2);
int Length(int Numbers[],int numbers);
using namespace std;
int LCS(char *s1,char *s2){
vector<int> Ts1,Ts2;
char *p1=s1,*p2=s2;
int i=0,j;
while(*p1!=NULL||*p2!=NULL){
Ts2.insert(Ts2.end(),0);
Ts1.insert(Ts1.end(),0);
j=0;
while(j<=i&&*p1!=NULL){
if(*(s2+j)!=NULL&&*(s2+j)==*p1&&Ts2[j]==0){
Ts2[j]=i+1;
Ts1[j]=-1;
break;
}
j++;
}
j=0;
while(j<=i&&*p2!=NULL){
if(*(s1+j)!=NULL&&*(s1+j)==*p2&&Ts1[j]==0){
Ts1[j]=i+1;
Ts2[j]=-1;
break;
}
j++;
}
p1++;
p2++;
i++;
}
int *Buff=new int[i];
int c=0,res;
j=0;
while(j<i){
if(Ts1[j]>0)
Buff[c++]=Ts1[j];
if(Ts2[j]>0)
Buff[c++]=Ts2[j];
j++;
}
res=Length(Buff,c);//Length做找Buff中最长子数列
delete Buff;
return res;
}
int Length(int Numbers[],int nNumbers){//直接找的eastcowboy的O(n*log(n))的算法(:
assert( nNumbers > 0 );
/* 尝试采用O(n*log(n))算法 */
int *buf = new int[nNumbers];
int i,j;
int max;
buf[0] = Numbers[0];
max = 1;
for(i=1; i<nNumbers; ++i)
{
/* 如果可以在原串中加入，则加入 */
if( Numbers[i] > buf[max-1] )
{
buf[max++] = Numbers[i];
continue;
}
/*
采用二分查找法在buf中寻找j，
使得buf[j-1] < Numbers[i] < buf[j]
定义buf[-1]为无穷小，即：当Number[i] < buf[0]时，j=0
*/
int low = 0;
int high = max;
while( low <= high )
{
j = (low+high)/2;
if( buf[j] == Numbers[i] )
break;
else if( buf[j] < Numbers[i] )
low = j + 1;
else
high = j - 1;
}
if( buf[j] == Numbers[i] )
continue;
j = low;
/* 修改最长子序列的内容，使之更“优”，可更容易的伸长 */
buf[j] = Numbers[i];
}
delete[] buf;
return max;
}
14 楼
rickone [专家分：15390] 发布于 2006-09-16 17:10:00
int LCS(char* str1,char* str2)
{
int n=strlen(str1);
int m=strlen(str2);
int *b=new int[n+1];
assert(b!=NULL);
memset(b,0,n+1);
for(int i=1;i<=m;++i)
{
int fw=0;
for(int j=1;j<=n;++j)
{
#define MAX(a,b) (a)>(b)?(a):(b)
int tmp;
if(str1[i-1]==str2[j-1])
{
tmp=fw;
fw=b[j-1]+1;
b[j-1]=tmp;
}
else
{
tmp=fw;
fw=MAX(fw,b[j]);
b[j-1]=tmp;
}
}
b[n]=fw;
}
int result=b[n];
if(b)
delete[]b;
return result;
}
//希望有更好的算法。。。
我来回复
您所在位置：