题意:
找出DNA序列中最长公共子串, 长度不小于3, 否则输出"no significant commonalities". 若等长有多个, 取字典序最小的.
思路:
若是最长公共子串, 每个串中都有, 因此可以只枚举第一个串(由于数据范围小, 先不考虑优化问题).
长度从小到大枚举(若是小的都不满足, 直接跳出判结果; 反之, 则需要一直试探, 找到第一个满足的长度即最大长度)
id 向后移动, 与其他串比较, 若有一个不含有, 则id继续移动. 若都含有, 为可疑答案, 存在ans中(细节注意).
wa了一次, 是循环边界的问题. 要注意.
kmp当然也可以, 但是不必要, 数据规模小.
#include <cstring> #include <cstdio> const int R = 11; const int C = 65; char s[R][C]; char t[C],ans[C]; //164K 16MS int main() { int T; scanf("%d",&T); while(T--) { int m; scanf("%d",&m); for(int i=0;i<m;i++) scanf("%s",s[i]); bool next_id,get_len,get = false; for(int len=3;len<=60;len++) { get_len = false; for(int id=0;id<=60-len;id++) { strncpy(t,&s[0][id],len); t[len] = '\0'; next_id = false; for(int i=1;i<m;i++) { if(!strstr(s[i],t)) { next_id = true; break; } } if(!next_id) { if(!get) get = true; if(!get_len) { get_len = true; strcpy(ans,t); } else if(strcmp(t,ans)<0) strcpy(ans,t); } } if(!get_len) break; } printf("%s\n",get?ans:"no significant commonalities"); } }