UVALive4513 Stammering Aliens（哈希法，后缀数组）

题目链接：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=12580

【思路】

求出现次数不小于k次的最长可重叠子串和最后的出现位置。

法一：

后缀数组，二分长度，划分height。时间复杂度为O(nlogn)

法二：

Hash法。构造字符串的hash函数，二分长度，求出hash(i,L)后排序，判断是否存在超过k个相同hash 值得块即可。时间为O(nlog²n).

　　法三：(UPD.16/4/6)

　　　　　SAM。求|right|。

注意划分height一定要精确且如果m=1需要特判

【代码1】

 //193ms

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 using namespace std;

 const int maxn = +; 

 int s[maxn];

 int sa[maxn],c[maxn],t[maxn],t2[maxn];

 void build_sa(int m,int n) {

     int i,*x=t,*y=t2;

     for(i=;i<m;i++) c[i]=;

     for(i=;i<n;i++) c[x[i]=s[i]]++;

     for(i=;i<m;i++) c[i]+=c[i-];

     for(i=n-;i>=;i--) sa[--c[x[i]]]=i;

     for(int k=;k<=n;k<<=) {

         int p=;

         for(i=n-k;i<n;i++) y[p++]=i;

         for(i=;i<n;i++) if(sa[i]>=k) y[p++]=sa[i]-k;

         for(i=;i<m;i++) c[i]=;

         for(i=;i<n;i++) c[x[y[i]]]++;

         for(i=;i<m;i++) c[i]+=c[i-];

         for(i=n-;i>=;i--) sa[--c[x[y[i]]]]=y[i];

         swap(x,y);

         p=; x[sa[]]=;

         for(i=;i<n;i++)

             x[sa[i]]=y[sa[i]]==y[sa[i-]] && y[sa[i]+k]==y[sa[i-]+k]?p-:p++;

         if(p>=n) break;

         m=p;

     }

 }

 int rank[maxn],height[maxn];

 void getHeight(int n) {

     int i,j,k=;

     for(i=;i<=n;i++) rank[sa[i]]=i;

     for(i=;i<n;i++) {

         if(k) k--;

         j=sa[rank[i]-];

         while(s[j+k]==s[i+k]) k++;

         height[rank[i]]=k;

     }

 }

 int limit,n,pos;

 bool can(int L) {    //一定要注意划分height数组的准确性

     pos=-;

     int cnt=,mx=sa[];

     for(int i=;i<=n;i++) {

         mx=max(mx,sa[i]);

         if(height[i]<L) cnt=,mx=sa[i];

         else {

             if(++cnt>=limit) pos=max(pos,mx);

         }

     }

     return pos>=;

 }

 char expr[maxn];

 int main() {

     //freopen("in.in","r",stdin);

     //freopen("out.out","w",stdout);

     while(scanf("%d",&limit)== && limit) {

         scanf("%s",expr);

         n=strlen(expr);

         for(int i=;i<n;i++) s[i]=expr[i]; s[n]=;

         build_sa('z'+,n+);

         getHeight(n);

         if(limit==) { printf("%d 0\n",n); continue; }

         int L=,R=n+;

         while(L<R) {

             int M=L+(R-L+)/;

             if(can(M)) L=M; else R=M-;

         }

         if(!can(L)) printf("none\n");

         else printf("%d %d\n",L,pos);

     }

     return ;

 }

【代码2】

 //1628ms

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 using namespace std;

 typedef unsigned long long ULL;

 const int maxn = +;

 const int x = ;

 ULL hash[maxn],xp[maxn],H[maxn];

 int m,n;

 char s[maxn];

 int cmp(const int& a,const int& b) {

     return hash[a]<hash[b] || (hash[a]==hash[b] && a<b);

 }

 int pos,rank[maxn];

 bool can(int L) {

     pos=-;

     for(int i=;i<n-L+;i++) hash[i]=H[i]-H[i+L]*xp[L],rank[i]=i;

     sort(rank,rank+n-L+,cmp);

     int cnt=;

     for(int i=;i<n-L+;i++) {

         if(!i || hash[rank[i]]!=hash[rank[i-]]) cnt=;

         if(++cnt>=m) pos=max(pos,rank[i]);

     }

     return pos>=;

 }

 int main() {

     //freopen("in.in","r",stdin);

     //freopen("outr.out","w",stdout);

     while(scanf("%d",&m)== && m) {

         scanf("%s",s);

         n=strlen(s);

         H[n]=,xp[]=;

         for(int i=n-;i>=;i--) H[i]=H[i+]*x+s[i]-'a';

         for(int i=;i<=n;i++) xp[i]=xp[i-]*x;

         if(!can()) printf("none\n");

         else {

             int L=,R=n+;

             while(L<R) {

                 int M=L+(R-L+)/;

                 if(can(M)) L=M;  else R=M-;

             }

             can(L);

             printf("%d %d\n",L,pos);

         }

     }

     return ;

 }

hash

巴特西

UVALive4513 Stammering Aliens（哈希法，后缀数组）

最新文章

热门文章