题目描述
求n个字符串的最长公共序列，，若长度相同，输出字典序最小的。若长度小于3，输出no significant commonalities
Sample Input32GATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA3GATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATAGATACTAGATACTAGATACTAGATACTAAAGGAAAGGGAAAAGGGGAAAAAGGGGGAAAAGATACCAGATACCAGATACCAGATACCAAAGGAAAGGGAAAAGGGGAAAAAGGGGGAAAA3CATCATCATCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCACATCATCATAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAACATCATCATTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
Sample Outputno significant commonalitiesAGATACCATCATCAT
解题思路
暴力0ms可过….用ans储存当前最优解。
下面是代码
#include <cstdio>#include <cstring>const int maxn = 61;int n;int anslen = 0;char ans[maxn];char s[4010][maxn];char p[maxn];//模式串int main(){int t;scanf("%d",&t);while(t–) {scanf("%d",&n);anslen = 0;for(int i = 0 ; i < n ; i ++) scanf("%s",s[i]);int len1 = strlen(s[0]);for(int i = 0 ; i < len1 ; i ++) {for(int j = i ; j < len1 ; j ++) {/** 模式串是s[0][i,i+1,…,j] */for(int k = i ; k <= j ; k ++) {p[k-i] = s[0][k];}p[j-i+1] = '\0';/** 模式串已就绪 */bool flag = true;//记录其他主串是否都有p串int len = j-i+1;//长度if(len < anslen) continue;for(int k = 1 ; k < n ; k ++) {if(strstr(s[k],p) == NULL) {flag = false;break;}}if(flag) {if(len == anslen) {//看字典序if(strcmp(p,ans) < 0) {strcpy(ans,p);}}else {strcpy(ans,p);anslen = len;}}}}if(anslen < 3) printf("no significant commonalities\n");else printf("%s\n",ans);}return 0;}
要做一个积极勇敢乐观的追梦人，永远不说消极的话，
