网站打不开了,看装修案例的网站,网站建设提案,网站在哪里【题目链接】 http://www.spoj.pl/problems/PHRASES/ 【题目大意】 求在每个字符串中出现至少两次的最长的子串 【题解】 注意到这么几个关键点#xff1a;最长#xff0c;至少两次#xff0c;每个字符串。 首先对于最长这个条件#xff0c;我们可以想到二分答案… 【题目链接】 http://www.spoj.pl/problems/PHRASES/ 【题目大意】 求在每个字符串中出现至少两次的最长的子串 【题解】 注意到这么几个关键点最长至少两次每个字符串。 首先对于最长这个条件我们可以想到二分答案 然后利用后缀数组所求得的三个数组判断是否满足条件。 其次是出现两次每次出现这个条件的时候 我们就应该要想到这是最大值最小值可以处理的 将出现在同一个字符串中的每个相同字符串的起始位置保存下来 如果最小值和最大值的差距超过二分长度L则表明在这个字符串中这个条件是可行的。 将所有的字符串通过拼接符连接在一起做一遍后缀数组 现在我们根据h数组将大于二分长度的前后后缀分为一组 每当存在分组中的后缀数量大于2*n 就说明这个字符串有可能是我们需要的答案那么对它进行检验 检验所有可能合法的字符串就可以完成对一个长度的判断了。 【代码】 #include cstdio
#include cstring
#include vector
#include algorithm
using namespace std;
const int N1000010;
int n,m,rank[N],sa[N],h[N],tmp[N],cnt[N],ans,a[N],s[N]; char str[N];
void suffixarray(int n,int m){int i,j,k;n;for(i0;i2*n5;i)rank[i]sa[i]h[i]tmp[i]0;for(i0;im;i)cnt[i]0;for(i0;in;i)cnt[rank[i]s[i]];for(i1;im;i)cnt[i]cnt[i-1];for(i0;in;i)sa[--cnt[rank[i]]]i;for(k1;kn;k1){for(i0;in;i){jsa[i]-k;if(j0)jn;tmp[cnt[rank[j]]]j;}sa[tmp[cnt[0]0]]j0;for(i1;in;i){if(rank[tmp[i]]!rank[tmp[i-1]]||rank[tmp[i]k]!rank[tmp[i-1]k])cnt[j]i;sa[tmp[i]]j;}memcpy(rank,sa,n*sizeof(int));memcpy(sa,tmp,n*sizeof(int));if(jn-1)break;}for(jrank[h[ik0]0];in-1;i,k)while(~ks[i]!s[sa[j-1]k])h[j]k--,jrank[sa[j]1];
}int first0,len[N],u,K;
vectorint S[N];
int Min[15],Max[15];
bool check(int L){int cur-1;for(int i1;iu;i){if(h[i]L)S[cur].clear();S[cur].push_back(i);}for(int i0;icur;i){if(S[i].size()2*n){memset(Min,-1,sizeof(Min));memset(Max,-1,sizeof(Max));for(int j0;jS[i].size();j){int kS[i][j];int xupper_bound(a,an1,sa[k])-a-1;Min[x]Min[x]-1?sa[k]:min(Min[x],sa[k]);Max[x]Max[x]-1?sa[k]:max(Max[x],sa[k]);}bool flag1;for(int i0;in;i){if(Min[i]-1||Max[i]-Min[i]L){flag0;break;}}if(flag)return 1;}}return 0;
}int T;
int main(){scanf(%d,T);while(T--){scanf(%d,n);int tmp200; u0;for(int i0;in;i){scanf(%s,str);len[i]strlen(str);for(int j0;jlen[i];j)s[u](int)str[j];s[u]tmp;}tmp0; s[u]0; //注意处理完的字符串最后封零for(int i0;in;i){a[i]tmp;if(in)tmptmp(i0?len[i]:len[i]1);}suffixarray(u,310);int l1,r10000,ans0;while(lr){int mid(lr)1;if(check(mid))ansmid,lmid1;else rmid-1;}printf(%d\n,ans);}return 0;
}转载于:https://www.cnblogs.com/forever97/p/PHRASES.html
