现有10个字符，每个字符串的长度为100个 字符，请用任意语言编写程序找出10个字符串都包含的最长的字串。

Question

题目描述

现有10个字符，每个字符串的长度为100个 字符，请用任意语言编写程序找出10个字符串都包含的最长的字串。

Answer 1

北大有个题目，除了数据不同其他基本一致， 你可以看一下 http://poj.org/problem?id=3080

题目的意思就是输入不超过十个字符串，每个字符串的长度不超过60，然后找出最长的公共子串，如果有好几个子串长度相同，就输出字典序最小的，如果公共子串的长度小于3就不输出了（因为是DNA)
你可以根据下面的程序修改一下

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int next[100];
void get_next(char *s,int next[])
{
    int len=strlen(s);
    int i=0,j=-1;
    next[0]=-1;
    while(i<len)
    {
        if(j==-1||s[i]==s[j]) i++,j++,next[i]=j;
        else j=next[j];
    }
}
int KMP(char *a,char *b)//a主串，b子串 返回值为a中与b匹配的第一个字母的位置(从0开始)
{
    get_next(b,next);//计算next
    int n=strlen(a),m=strlen(b);
    int i=0,j=0;
    while(i<n&&j<m)
    {
        if(j==-1||a[i]==b[j]) i++,j++;
        else j=next[j];
    }
    if(j>=m) return i-m;
    return -1;
}
int KMP_Count(char *a,char *b)//a主串，b子串 返回值为共有a中多少个与b匹配的子串
{
    get_next(b,next);//计算next
    int n=strlen(a),m=strlen(b);
    int i=0,j=0;
    int cnt=0;
    while(i<n&&j<m)
    {
        if(j==-1||a[i]==b[j]) i++,j++;
        else j=next[j];
        if(j==m) cnt++,j=next[j];
    }
    return cnt;
}
char map[100][100];
char s[100],_max[100],res;
int main()
{
    int ci;scanf("%d",&ci);
    while(ci--)
    {
        _max[0]='/0';res=0;
        int n;scanf("%d",&n);
        for(int i=0;i<n;i++) scanf("%s",map[i]);
        for(int i=0,len=strlen(map[0]);i<len;i++)
        {
            for(int j=i;j<len;j++)
            {
                int l=0;
                for(int k=i;k<=j;k++) s[l++]=map[0][k];s[l]='/0';
                int flag=1;
                for(int i=1;i<n;i++)
                {
                    if(KMP(map[i],s)==-1)
                    {
                        flag=0;break;
                    }
                }
                if(flag)
                {
                    if(l>res) res=l,strcpy(_max,s);
                    else if(l==res)
                    {
                        if(strcmp(s,_max)<0) strcpy(_max,s);
                    }
                }
            }
        }
        if(res<3) printf("no significant commonalities/n");
        else printf("%s/n",_max);
    }
    return 0;
}

Answer 2

能想到的办法是转换成为：“获取其中任意两个字符串的公共子序列，再对于剩下的字符串进行查找子序列的操作”

Answer 3

思路

10个字符串分别截取每一位，对每一位的值进行竖向比较 ， 如果都是一样的，那么将这个值保留下来

str_1 =  "1234567890"
str_2 =  "1235486332"
str_3 =  "1234567890"
str_4 =  "1234567890"
str_5 =  "1234567890"
str_6 =  "1234567890"
str_7 =  "1234567890"
str_8 =  "1234567890"
str_9 =  "1234567890"
str_10 = "1234567890"

res = []

daiding = set()
for i in range(10):
    str_1_1 = str_1[i]
    str_2_1 = str_2[i]
    str_3_1 = str_3[i]
    str_4_1 = str_4[i]
    str_5_1 = str_5[i]
    str_6_1 = str_6[i]
    str_7_1 = str_7[i]
    str_8_1 = str_8[i]
    str_9_1 = str_9[i]
    str_10_1 = str_10[i]
    daiding.add(str_1_1)
    daiding.add(str_2_1)
    daiding.add(str_3_1)
    daiding.add(str_4_1)
    daiding.add(str_5_1)
    daiding.add(str_6_1)
    daiding.add(str_7_1)
    daiding.add(str_8_1)
    daiding.add(str_9_1)
    daiding.add(str_10_1)

    if daiding.__len__() ==1:
        res.append(str_1_1)
    daiding.clear()

print(res)