求交集(串)
时间: 1ms 内存:1M
描述:
设有集合A和集合B,求A∩B的最长子集。
输入:
A:asdfghjkla
B:wesdfghjeteya
A:I likeyou!
B:Realy,but I like your hat.It's cool!
输出:
sdfghj
I like you
示例输入:
Hi,those are yours.
Un,no,those arn't mine.
示例输出:
,those ar
提示:
参考答案(内存最优[752]):
#include <stdio.h>
int main(){
char c[100],d[100];
int i,j,k,max=1,pre=0,sum;
gets(c);
getchar();
gets(d);
for(i=0;c[i]!=0;i++){
sum=0;
k=i;
for(j=0;d[j]!=0;){
if(c[k]==d[j]){
sum++;
k++;
j++;
if(c[k]==0)
break;
}
else{
k=i;
if(sum>max){
max=sum;
pre=i;
}
sum=0;
while(d[j]!=c[k]){
j++;
if(d[j]==0)
break;
}
}
}
if(sum>max){
max=sum;
pre=i;
}
}
for(i=pre;i<pre+max;i++)
printf("%c",c[i]);
return 0;
}
参考答案(时间最优[4]):
#include <stdio.h>
int main(){
char c[100],d[100];
int i,j,k,max=1,pre=0,sum;
gets(c);
getchar();
gets(d);
for(i=0;c[i]!=0;i++){
sum=0;
k=i;
for(j=0;d[j]!=0;){
if(c[k]==d[j]){
sum++;
k++;
j++;
if(c[k]==0)
break;
}
else{
k=i;
if(sum>max){
max=sum;
pre=i;
}
sum=0;
while(d[j]!=c[k]){
j++;
if(d[j]==0)
break;
}
}
}
if(sum>max){
max=sum;
pre=i;
}
}
for(i=pre;i<pre+max;i++)
printf("%c",c[i]);
return 0;
}
题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。