主题：第62次编程比赛
雨中飞燕 [专家分：18980] 发布于 2008-01-11 16:49:00
考虑到现在处于期末考试阶段，本次比赛结束时间会迟些，目前定于1月19日晚上12时结束。结束后偶会发解题报告。
[size=3]题目：最长公共子序列 ★★★★★★[/size]
[color=0000FF]题目描述：[/color]
给定一个序列a,b,c,d,e,f,g，
其子序列的定义就是在当中任意删掉若干个元素，
例如a,b,e,g就是其中一个子序列。
现给定两个字符串，要求出它们的最长公共子序列的长度
[color=0000FF]输入：[/color]
多组测试数据，每两个字符串组成一组，
中间用空格或者换行符分隔
单个字符串最大长度为200000字节，或者100000个全角(或混合)字符。
以EOF标志结束输入。
[color=0000FF]输出：[/color]
对于每组测试数据，输出一行，每行仅输出一个数，
表示它们的最长公共子序列的长度
[color=0000FF]样例输入：[/color]
大家好 才是真的好
abcdefg acegbdf
天气真是好 这个天气就是好
Congratulations 恭喜你
[color=0000FF]样例输出：[/color]
1
4
4
0
[color=0000FF]其它信息：[/color]
连续两个ascii>127的字符应当视为全角字符对待，要看成一个整体。
但如果相邻两个一个>127，但另一个在127以内，那么这两个
不应该作为全角字符看待。
[color=FF0000]代码提交[/color]：请把您的完整代码直接回复于本帖子，回复帖子将不可见，
但在结帖以前你仍然可以编辑您的帖子。
如果您希望能够马上测试您的代码，请提交到[url]http://yzfy.org/bbs/viewthread.php?tid=611[/url]
如果对题目有任何疑问，请在提问帖子[url]http://www.programfan.com/club/post-265092.html[/url]里问。
回复列表 （共11个回复）
沙发
diaoxue [专家分：600] 发布于 2008-01-11 17:50:00
此程序仅用于英文字串，输入还得改，占个地方。
[code=c]
/*Input the length of the two string(m&n):
8 7
Input the first string:
a b c b d a b
Input the second string:
b d c a b a
Press any key to continue
*/
#include<iostream>
using namespace std;
void LcsLength(char *x,char *y,int *c[],int m,int n)
{
for(int i=0;i<m;i++)
c[i][0]=0;
for(int j=0;j<n;j++)
c[0][j]=0;
for(i=1;i<m;i++)
{
for(j=1;j<n;j++)
{
if(x[i]==y[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];
}
}
}
}
int main()
{
int i,j;
int m,n;
int l,k;
cout<<"Input the length of the two string(l&k):"<<endl;
// cin>>m>>n;
cin>>l>>k;
m=l+1;
n=k+1;
char *x,
*y;
x=new char[m];
y=new char[n];
cout<<"Input the first string:"<<endl;
for(i=1;i<m;i++)
cin>>x[i];
cout<<"Input the second string:"<<endl;
for(j=1;j<n;j++)
cin>>y[j];
int **c;
c=new int*[m];
for(i=0;i<m;i++)
c[i]=new int[n];
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
c[i][j]=0;
}
LcsLength(x,y,c,m,n);
int max=c[l][k];
cout<<max<<endl;
delete [] x;
x=NULL;
delete [] y;
y=NULL;
for(i=0;i<m;i++)
delete []c[i];
delete []c;
c=NULL;
return 0;
}
[/code]
板凳
plane [专家分：310] 发布于 2008-01-11 19:59:00
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
unsigned char a[200001],b[200001];
int **p,str1[200001],str2[200001];
int main(){
int l1,l2,i,j,sum;
while(scanf("%s %s",a,b)!=EOF){
for(i=0,l1=0,l2=0,j=0;a[i]&&b[j];){
if(a[i]>127&&a[i+1]>127){
str1[l1++]=a[i]*1000+a[i+1];
i+=2;
}
else{
str1[l1++]=a[i];
i++;
}
if(b[j]>127&&b[j+1]>127){
str2[l2++]=b[j]*1000+b[j+1];
j+=2;
}
else{
str2[l2++]=b[j];
j++;
}
}
if(a[i]){
while(a[i]){
if(a[i]>127&&a[i+1]>127){
str1[l1++]=a[i]*1000+a[i+1];
i+=2;
}
else{
str1[l1++]=a[i];
i++;
}}
}
else if(b[j]){
while(b[j]){
if(b[j]>127&&b[j+1]>127){
str2[l2++]=b[j]*1000+b[j+1];
j+=2;
}
else{
str2[l2++]=b[j];
j++;
}}
}
p=(int**)malloc(sizeof(int*)*(l1+1));
p[0]=(int*)malloc(sizeof(int)*(l2+1));
memset(p[0],0,sizeof(int)*(l2+1));
for(i=1;i<=l1;i++){
p[i]=(int*)malloc(sizeof(int)*(l2+1));
p[i][0]=0;
}
for(i=1;i<=l1;i++)
for(j=1;j<=l2;j++){
if(str1[i-1]==str2[j-1])
p[i][j]=p[i-1][j-1]+1;
else if(p[i-1][j]>=p[i][j-1])
p[i][j]=p[i-1][j];
else
p[i][j]=p[i][j-1];
}
printf("%d\n",p[l1][l2]);
delete p;
}
return 0;
}
3 楼
ws0415 [专家分：3370] 发布于 2008-01-11 21:25:00
[code=c]
#include <iostream>
using namespace std;
#define M(x,y) x>y?x:y
int Maxset(char* s1,char *s2)
{
if(*s1==0||*s2==0)
return 0;
if(*s1==*s2)
return 1+Maxset(++s1,++s2);
else
{
char *p1=s1;
char *p2=s2;
int i=Maxset(++p1,s2);
int j=Maxset(s1,++p2);
return M(i,j);
}
}
int main()
{
char s1[100],s2[100];
while(gets(s1)&&gets(s2))
{
cout<<Maxset(s1,s2)<<endl;
}
return 0;
}[/code]
4 楼
kingofmiaomiao [专家分：0] 发布于 2008-01-12 22:42:00
[code]
#include <stdio.h>
#include <string.h>
#define L 200000
int c[2][L];
int
lcsl(const char * s1,int s1l,const char * s2,int s2l)
{
int i,j,xl,yl,yy=0;
const char *x,*y;
s1l<s2l?((x=s1),(xl=s1l),(y=s2),(yl=s2l)):((y=s1),(yl=s1l),(x=s2),(xl=s2l));
for(i=0;i<yl;++i)c[0][i]=c[1][i]=0;
for(i=1;i<=xl;++i){
if(yy&&i>=2&&0>x[i-1]&&0>x[i-2]){
for(j=1;j<=yl;++j){
((3+i)%2)?(c[0][j]=c[1][j]):(c[1][j]=c[0][j]);
}
yy=0;
}else if((2+i)%2){
for(j=1;j<=yl;++j){
if(x[i-1]==y[j-1]){
c[1][j]=c[0][j-1]+1;
if((0>x[i-1])&&(0>x[i])&&(x[i]==y[j])){
c[1][j+1]=c[0][j-1]+1;
yy=1;++j;
}
}else{
c[1][j]=(c[0][j]>=c[1][j-1])?c[0][j]:c[1][j-1];
}
}
}else{
for(j=1;j<=yl;++j){
if(x[i-1]==y[j-1]){
c[0][j]=c[1][j-1]+1;
if((0>x[i-1])&&(0>x[i])&&(x[i]==y[j])){
c[0][j+1]=c[1][j-1]+1;
yy=1;++j;
}
}else{
c[0][j]=(c[1][j]>=c[0][j-1])?c[1][j]:c[0][j-1];
}
}
}
}
return c[(2+xl)%2][yl];
}
int
main(void)
{
char x[L],y[L];
while(1){
fscanf(stdin,"%s%s",x,y);
fprintf(stdout,"%d\n",lcsl(x,strlen(x),y,strlen(y)));
}
return 0;
}
[/code]
:PP
5 楼
javacfish [专家分：0] 发布于 2008-01-13 22:15:00
看看
7 楼
mingda [专家分：220] 发布于 2008-01-16 08:39:00
如果某一组本身有重复的字符，怎么处理？
8 楼
mingda [专家分：220] 发布于 2008-01-16 08:52:00
#include <iostream>
using namespace std;
void main(void)
{
cout<<"Input the first string.."<<endl;
unsigned char arr[200000][2],brr[200000][2]; //第二位：0、半角；1、全角前半；2、全角后半
unsigned long i=0,s_arr=0,j=0,s_brr=0,s_add=0;
//------------------------------------------------
while(1)
{
cin>>arr[i][0];
if(arr[i][0]=='#')
break;
i++;
s_arr++;
}
cout<<"Input the second string.."<<endl;
while(1)
{
cin>>brr[j][0];
if(brr[j][0]=='#')
break;
j++;
s_brr++;
}
//------------------------------------------------
if(arr[0][0]>127) arr[0][1]=1;
else arr[0][1]=0;
for(i=1;i<s_arr;i++)
{
if(arr[i][0]>127)
{
if(arr[i-1][1]==1) arr[i][1]=2;
else if(arr[i+1][0]>127) arr[i][1]=1;
else arr[i][1]=0;
}
else arr[i][1]=0;
}
//------------------------------------------------
if(brr[0][0]>127) brr[0][1]=1;
else brr[0][1]=0;
for(j=1;j<s_brr;j++)
{
if(brr[j][0]>127)
{
if(brr[j-1][1]==1) brr[j][1]=2;
else if(brr[j+1][0]>127) brr[j][1]=1;
else brr[j][1]=0;
}
else brr[j][1]=0;
}
unsigned long tempj=0; //第二组有相同字符时的位置
for(i=0;i<s_arr;i++)
for(j=tempj;j<s_brr;j++)
{
if(arr[i][1]==brr[j][1])
{
if(arr[i][1]==0 && arr[i][0]==brr[j][0])
{
s_add++;
tempj=j+1;
break;
}
if(arr[i][1]==1 && arr[i][0]==brr[j][0] && arr[i+1][0]==brr[j+1][0])
{
s_add++;
tempj=j+2;
break;
}
}
}
cout<<"s_add is "<<s_add<<endl; //答案
cout<<"s_arr is "<<s_arr<<endl; //第一组的长度
cout<<"s_brr is "<<s_brr<<endl; //第二组的长度
return;
}
有一个问题就是我用while(cin>>arr[i][0])用来结束输入总是出问题（输入CTRL+Z结束），所以我改为用'#'号来结束输入。
请点评，谢谢！
9 楼
yxs0001 [专家分：9560] 发布于 2008-01-18 13:13:00
#include <iostream>
#include <ctime>
using namespace std;
int MaxLen(unsigned short x[],unsigned short y[],int lenx,int leny)
{
unsigned short *px,*py; //分别指向长短数组
int *plx,*ply; //长短数组的长度指针
int *c0; //矩阵
int *c1;
int j = 0;
//寻找短数组
if(lenx>leny)
{
px = x;
py = y;
plx = &lenx;
ply = &leny;
}
else
{
px = y;
py = x;
plx = &leny;
ply = &lenx;
}
//初始化
c0 = new int [*ply + 1];
c1 = new int [*ply + 1];
for (j=0;j<*ply + 1;j++)
c0[j] = c1[j] = 0;
//计算
// if(x[i] = y[j]) c[i][j] = c[i-1][j-1] + 1
// else
// c[i][j] = max(c[i][j-1],c[i-1][j])
for(int i=1;i<=*plx;i++)
{
for(j=1;j<=*ply;j++)
{
if(px[i-1] == py[j-1])
c1[j] = c0[j-1] + 1;
else
c1[j] = (c1[j-1] > c0[j] ? c1[j-1] : c0[j]);
}
for(j=0;j<=*ply;j++)
{
c0[j] = c1[j];
}
}
return c1[*ply];
}
int main(void)
{
unsigned short x[200000] = {0}; //存储转换字符串X
unsigned short y[200000] = {0}; //存储转换字符串Y
int lenx = 0,leny = 0; //X Y 长度
unsigned char c = 0,pro = 0; //当前读取字符 前一个字符
bool bU = false; //全角标记
int words = 0; //字符串数
unsigned short *p = x; //指针
int *plen = &lenx;
while(c = unsigned(cin.get()))
{
//当前字符 > 127
if(c>127)
{
//前一个字符 > 127
//作为全角字符入数组
if(bU)
{
p[*plen] = c * pro;
(*plen) ++;
bU = false;
}
//前一字符 < 127
//暂存并作标记
else
{
pro = c;
bU = true;
}
}
//半角字符处理
else if(c>32)
{
//前一个字符 > 127
//前一字符入数组
if(bU)
{
p[*plen] = pro;
(*plen) ++;
bU = false;
}
//当前字符入数组
p[*plen] = c;
(*plen) ++;
}
//特殊字符处理
else
{
//前一个字符 > 127
//前一字符入数组
if(bU)
{
p[*plen] = pro;
(*plen) ++;
bU = false;
}
//处理间隔符、结束符
if(char(c) == '\n' || char(c) == ' ' || char(c) == EOF)
{
words ++;
if(words & 1)
{
p = y;
plen = &leny;
}
else
{
p = x;
plen = &lenx;
cout<<MaxLen(x,y,lenx,leny)<<'\n';
lenx = leny = 0;
}
}
if(char(c) == EOF)
break;
}
}
/*
srand( (unsigned)time( NULL ) );
while(true){
for(int i=0;i<200000;i++)
{
x[i] = rand() % 60000;
y[i] = rand() % 60000;
}
lenx = rand() % 10000 + 190000;
leny = rand() % 5000 + 150000;
cout<< lenx<<" "<<leny<<endl;
cout<<MaxLen(x,y,lenx,leny)<<endl;
cin>>c;}*/
return 0;
}
10 楼
华山论剑 [专家分：5310] 发布于 2008-01-19 18:39:00
[code=c]
#include <stdio.h>
#include <string.h>
#include <malloc.h>
#define MAX_LEN 200001
int x[MAX_LEN], y[MAX_LEN];
int LCS(char *a, char *b)
{
int m = strlen(a) - 1, n = strlen(b) - 1;
int i, j, size = sizeof(int) * (n + 2); //上面减的1加上+1空字符
memset(x, 0, size); //加这2句避免逐位循环填0
memset(y, 0, size);
for (i=m; i>=0; --i)
{
for (j=n; j>=0; --j)
{
if (a[i]==b[j])
{
if (a[i]>0 || (a[i]<0 && a[i-1]==b[j-1]))
x[j] = 1 + y[j+1]; //ASCII和汉字2字节都相等则添加
else
x[j] = y[j] > x[j+1] ? y[j] : x[j+1];
if (a[i]<0)
x[--j] = x[j+1]; //b串中如是汉字当作整体
}
else
{
x[j] = y[j] > x[j+1] ? y[j] : x[j+1];
if (b[j]<0)
x[--j] = x[j+1]; //b串中如是汉字当作整体
}
}
if (a[i]<0) //a串中如是汉字当作整体
--i;
memcpy(y, x, size); //复制x到y
}
return x[0];
}
int main()
{
char s1[MAX_LEN], s2[MAX_LEN];
while (gets(s1)!=NULL)
{
gets(s2);
printf("%d\n", LCS(s1, s2));
}
return 0;
}
[/code]
说明：
1、基于DP的解法，时间复杂度O(mn)，空间复杂度O(2n);
2、用memset代替逐位循环填充a[i]==0||b[i]==0，可以快8％左右;
3、辅助的int数组x、y声明成全局变量，相比用new动态声明，在字串很短的时候经测试空间只多占8K左右(总共608K)，字串长时两种方式空间就没多大区别了，20万字长时内存总共占用2.5M左右。速度上动态声明的更慢;
4、如果20万长度的字串，时间要270多秒(2.8G 1G RAM)，对于1000ms的要求无论如何是达不到，所以代码姑且贴上。
我来回复
您所在位置：