求交集(串)

求交集(串)

时间: 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; 
}

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

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注