上海建筑设计公司网站,机械网站开发,湖南省住房与城乡建设网站,php wordpress apache题目大意#xff1a; 求出这些DNA序列中的最长且字典序最小的公共子串。 思路分析#xff1a; 二分长度的答案#xff0c;去height中扫描这个长度是否满足#xff0c;一旦满足就立即输出。这样就能够保证字典序最小了。 #include cstdio
#include iostream… 题目大意 求出这些DNA序列中的最长且字典序最小的公共子串。 思路分析 二分长度的答案去height中扫描这个长度是否满足一旦满足就立即输出。这样就能够保证字典序最小了。 #include cstdio
#include iostream
#include cstring
#include algorithm
#define maxn 1005
using namespace std;char str[maxn];
int sa[maxn],t1[maxn],t2[maxn],c[maxn],n;void suffix(int m)
{int *xt1,*yt2;for(int i0;im;i)c[i]0;for(int i0;in;i)c[x[i]str[i]];for(int i1;im;i)c[i]c[i-1];for(int in-1;i0;i--)sa[--c[x[i]]]i;for(int k1;kn;k1){int p0;for(int in-k;in;i)y[p]i;for(int i0;in;i)if(sa[i]k)y[p]sa[i]-k;for(int i0;im;i)c[i]0;for(int i0;in;i)c[x[y[i]]];for(int i0;im;i)c[i]c[i-1];for(int in-1;i0;i--)sa[--c[x[y[i]]]]y[i];swap(x,y);p1;x[sa[0]]0;for(int i1;in;i)x[sa[i]]y[sa[i-1]]y[sa[i]]y[sa[i-1]k]y[sa[i]k]?p-1:p;if(pn)break;mp;}
}
int rank[maxn],height[maxn];
void getheight()
{int k0;for(int i0;in;i)rank[sa[i]]i;for(int i0;in;i){if(k)k--;if(!rank[i])continue;int jsa[rank[i]-1];while(str[ik]str[jk])k;height[rank[i]]k;}
}
int pos,N,fans;
bool vis[20];
int bel[maxn];bool ok()
{for(int i1;iN;i)if(!vis[i])return false;return true;
}
bool check(int len)
{pos-1;memset(vis,false,sizeof vis);int i;for(i1;in;i){if( height[i]len ){if(ok()){possa[i-1];return true;}memset(vis,false,sizeof vis);}else{if(!vis[bel[sa[i-1]]])vis[bel[sa[i-1]]]true;if(!vis[bel[sa[i]]])vis[bel[sa[i]]]true;if(ok()){possa[i];return true;}}}if(ok())possa[i-1];return pos!-1;
}
char tmp[100];
int main()
{int T;scanf(%d,T);while(T--){scanf(%d,N);int top0;for(int i1;iN;i){scanf(%s,tmp);for(int j0;j60;j){bel[top]i;str[top]tmp[j];}bel[top]i;str[top]127-i;}str[top-1]0;ntop;suffix(128);getheight();int l3,r60,mid,ans0;while(lr){mid(lr)1;if(check(mid))ansmid,fanspos,lmid1;else rmid-1;}if(ans3)printf(no significant commonalities);else{for(int ifans;ifansans;i)printf(%c,str[i]);}puts();}return 0;
}转载于:https://www.cnblogs.com/gavanwanggw/p/6884058.html
