主题：第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个回复）
沙发
BigCarrot [专家分：10] 发布于 2006-09-14 21:45:00
test
板凳
argentmoon [专家分：13260] 发布于 2006-09-14 22:06:00
int LCS(char* str1, char* str2)
{
int len1 = strlen(str1), len2 = strlen(str2);
int table[2][30000], now = 0, i, j;
memset(table, 0, sizeof(table));
for(i = 0; i < len1; i++, now = !now) for(j = 0 ; j < len2; j++){
if(str1[i] == str2[j])
table[now][j + 1] = table[!now][j] + 1;
else
table[now][j + 1] = table[now][j] > table[!now][j + 1] ? table[now][j] : table[!now][j + 1];
}
return table[!now][len2];
}
3 楼
magicalking [专家分：150] 发布于 2006-09-15 14:15:00
#include<iostream>
#include<utility>
#include<vector>
#define OCC '0'
using namespace std;
typedef pair<int,int> eq_t;
int LCS(string str1, string str2){
int pos=0,pos_end=str1.size(),pos2,pos2_end=str2.size(),cn=0;
vector<eq_t> pair_c;
for(;pos<pos_end;pos++)
for(pos2=0;pos2<pos2_end;pos2++)if(str1[pos]==str2[pos2]){
pair_c.push_back(make_pair(pos,pos2));
str2[pos2]=OCC;
}
if(!pair_c.empty()){
cn++;
vector<eq_t>::iterator vit=pair_c.begin(),vit_end=pair_c.end()-1;
while(vit!=vit_end){
if(vit->first<(vit+1)->first&&vit->second<(vit+1)->second)cn++;
vit++;
}
}
return cn;
}
4 楼
magicalking [专家分：150] 发布于 2006-09-15 14:19:00
偶没用char*,用了string,应该不算违反题意吧
5 楼
willzhanglala [专家分：1350] 发布于 2006-09-15 16:09:00
int LCS(const char * str1, const char * str2)
{
int len1=strlen(str1);
int len2=strlen(str2);
int len=(len1>len2)?len2:len1;
int * table=new int[len+1];
memset(table,0,(len+1)*4);
__int64 count=0;
int tablesize=0;
int tablebegin=0;
for(int i=0;i<len1;i++)
{
bool breakj=false;
for(int j=tablebegin;j<=tablesize;j++)
{
for(int k=table[j];k<len2;k++)
{
if(str1[i]==str2[k])
{
if(table[j+1]==0)
{
table[j+1]=k+1;
tablesize++;
breakj=true;
}
else
table[j+1]=(table[j+1]<k+1)?table[j+1]:k+1;
break;
}
}
//count ++;
if(breakj)
break;
}
int newtablebegin=(tablesize-(len1-i-1));
tablebegin=(tablebegin>newtablebegin)?tablebegin:newtablebegin;
for (int j=tablebegin;j<tablesize;j++)
{
if(table[j]>=table[j+1]-1)
{
tablebegin++;
}
else
break;
}
//cout<<i<<","<<tablebegin<<endl;
}
cout<<endl;
delete table;
//printf("%d ",count);
return tablesize;
}
6 楼
hotzenplotz [专家分：40] 发布于 2006-09-15 17:57:00
这是我的程序，第一次参加，请大家指教。
int digui (char* str1,char* str2,int step)
{
// printf("the str1 is %s",str1);
// printf(" the str2 is %s",str2);
// printf(" the step is %d\n",step);
int i2=strlen(str2);
if (0==i2)
{
// printf("the end!!\n");
return step;
}
if (i2>strlen(str1))
{
// printf("the wrong!!\n");
return 0;
}
char *ptr;
ptr=strchr(str1, *str2);
if (ptr)
{
int a=digui(str1,++str2,step);
int b=digui(++ptr,str2,step+1);
if (a>b)
{
//printf("return a!!\n");
return a;
}
else
{
// printf("return b!!\n");
return b;
}
}
else return digui(str1,++str2,step);
}
int LCS(char* str1,char* str2)
{
if (strlen(str1)<strlen(str2))
{
char* strtemp;
strtemp=str1;
str1=str2;
str2=strtemp;
}
return digui(str1,str2,0);
}
7 楼
孤独的猫 [专家分：3370] 发布于 2006-09-15 20:41:00
int LCS(char* str1, char* str2)
{
int *s1,*s2,*temp,len1,len2;
int i,j,res=0;
len1=strlen(str1);
len2=strlen(str2);
s1=(int*)malloc(len1*sizeof(int*));
s2=(int*)malloc(len1*sizeof(int*));
for(i=0;i<len1;i++)
{
s1[i]=str1[i]==str2[0]?1:0;
}
for(j=1;j<len2;j++)
{
s2[0]=str1[0]==str2[j]?1:0;
for(i=1;i<len1;i++)
{
if(str1[i]==str2[j])
{
s2[i]=s1[i-1]?s1[i-1]+1:1;
if(s2[i]>res)res=s2[i];
}
else
{
s2[i]=0;
}
}
temp=s1;
s1=s2;
s2=temp;
}
free(s1);
free(s2);
return res;
}
8 楼
qantas18 [专家分：30] 发布于 2006-09-15 23:22:00
/*第一次参加，感觉比较难啊，可能我比较菜，想了好久，想不到更好的解决方法，这个肯定不行，算法不好，太慢了。字符长度增加到二十几的时候就要好几秒，再多就算不出来了，不过贴出来，希望学习下高手是怎么解决的*/
int LCS(char* str1, char* str2)
{
int max,top;
char *pstr1 ;
char *pstr2 ;
char *stack1[20000]; //怕麻烦不用链表了，呵呵
char *stack2[20000];
pstr1 = str1;
pstr2 = str2;
max = 0;
top = 0;
while(*pstr1 != '\0')
{
while(*pstr2 != '\0')
{
if (*pstr1 == *pstr2)
goto out1;
else
pstr2++;
}
pstr1++;
}
out1:
stack1[++top] = pstr1++;
stack2[top] = pstr2++;
max = top;
while(top > 0)
{
while(*pstr1 != '\0')
{
while(*pstr2 != '\0')
{
if(*pstr1 == *pstr2)
{
stack1[++top] = pstr1 ++;
stack2[top] = pstr2 ++;
if(top > max) max = top;
}
else
pstr2 ++;
}
pstr1 ++;
pstr2 = stack2[top];
pstr2 ++;
}
pstr1 = stack1[top--];
pstr2 = stack2[top];
pstr1 ++;
pstr2 ++;
}
//---------------------------------------------------
pstr1 = str2;
pstr2 = str1;
top = 0;
while(*pstr1 != '\0')
{
while(*pstr2 != '\0')
{
if (*pstr1 == *pstr2)
goto out2;
else
pstr2++;
}
pstr1++;
}
out2:
stack1[++top] = pstr1++;
stack2[top] = pstr2++;
if(top > max) max = top;
while(top > 0)
{
while(*pstr1 != '\0')
{
while(*pstr2 != '\0')
{
if(*pstr1 == *pstr2)
{
stack1[++top] = pstr1 ++;
stack2[top] = pstr2 ++;
if(top > max) max = top;
}
else
pstr2 ++;
}
pstr1 ++;
pstr2 = stack2[top];
pstr2 ++;
}
pstr1 = stack1[top--];
pstr2 = stack2[top];
pstr1 ++;
pstr2 ++;
}
//-----------------------------------------------------------
return max;
}
9 楼
WinWing [专家分：3450] 发布于 2006-09-16 03:53:00
#include<iostream>
using namespace std;
int LCS(char* str1, char* str2)
{
int i,j,m,n,RetVal;
m = strlen(str1);
n = strlen(str2);
int **c = new int*[m+1];
for(i=0;i<=m;i++)
c[i] = new int[n+1];
for (i=1;i<=m; ++i)
c[i][0]=0;
for (i=0;i<=n; ++i)
c[0][i]=0;
for (i=1;i<=m; ++i)
{
for (j=1;j<=n;++j)
{
if (str1[i]==str2[j])
c[i][j]=c[i-1][j-1]+1;
else if (c[i-1][j]>=c[i][j-1])
c[i][j]=c[i-1][j];
else
c[i][j]=c[i][j-1];
}
}
RetVal = c[m][n];
for (i=0; i<=m; ++i)
delete[] c[i];
delete[] c;
return RetVal;
}
10 楼
willzhanglala [专家分：1350] 发布于 2006-09-16 09:48:00
A more efficient way.
int LCS(const char * str1, const char * str2)
{
int len1=strlen(str1);
int len2=strlen(str2);
if(len1>len2)
{
const char * tmp;
tmp=str1;
str1=str2;
str2=tmp;
len1^=len2;
len2^=len1;
len1^=len2;
}
int * table= new int[len1+1];
memset(table,0,(len1+1)*4);
int tablebegin=0;
int tablesize=0;
for (int i=0;i<len1;i++)
{
for (int j=tablebegin;j<=tablesize;j++)
{
if(table[j]&0x80000000)
continue;
int k=table[j];
if(str1[i]==str2[k])
{
table[j]|=0x80000000;
table[j+1]=k+1;
if(j==k)
tablebegin=j+1;
if(j==tablesize)
{
tablesize++;
break;
}
continue;
}
k++;
bool breakj=false;
for(;k<len2;k++)
{
if(str1[i]==str2[k])
{
if(table[j+1]==0)
{
table[j+1]=k+1;
tablesize++;
breakj=true;
}
else
{
int tmp=table[j+1]&0x7fffffff;
table[j+1]=(tmp<=k+1)?table[j+1]:k+1;
}
break;
}
}
if(breakj)
break;
}
int newtablebegin=tablesize-(len1-i);
tablebegin=(tablebegin>newtablebegin)?tablebegin:newtablebegin;
}
delete table;
return tablesize;
}
我来回复
您所在位置：