首页 > 代码库 > poj 1509 Glass Beads
poj 1509 Glass Beads
题意：给你一个长度为n的字符串环，以位置i开始的顺时针长度为n的环构成的字符串有n个，问其中最小字典序的开始位置，有多种解时，输出起始位置最小的。
分析：
首先可以直接拼接两个长度为n的字符串，设原串为S[0],S[1]...S[n-1]则拼接后就是S‘=S[0],S[1],...S[n-1],S[0],S[1],...S[n-1]。
那么问题中的n个长度为n的字符串中的任意一个，一定存在S‘的某个后缀字符串的前缀与其相等。
我们现在要找最小字典序，则可以直接先求S‘的后缀数组SA，然后:
1、找到第一个SA[i]<n的i
2、可以知道SA[i]一定是字典序最小的后缀，但题目要求有多种解时，输出起始位置最小的。
这个怎么搞呢？其实也蛮简单的，对于所有前n个字符字典序相同的后缀字符串，在SA中一定是相邻的。
所以只要判断LCP[i]是不是大于等于n就可以知道该后缀的长度为n个前缀是不是整体上字典序最小的了。
所以可以这么搞：
while（LCP[i]>=n){
i++;
update(ans);
}
3、输出ans就可以了。其实也可以不update(ans)，最后一个满足LCP[i]>=n的i对应的SA[i]一定是答案。
因为前n个字符相同的所有后缀排在后面的一定比排在前面的长
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <queue> 6 #include <string> 7 #include <vector> 8 #include <cmath> 9 #include <set>10 #define maxn 200001011 #define maxm 201012 #define maxt 11013 #define INF 0x3f3f3f3f14 #define mod 100915 #define MAX_STATE 250016 using namespace std;17 int n,k;18 int Rank[maxn];19 int temp[maxn];20 int LCP[maxn];21 int SA[maxn];22 //比较(rank[k,i],rank[k,i+k])与(rank[k,j],rank[k,j+k])23 bool cmp_sa(int i,int j){24 if(Rank[i]!=Rank[j])return Rank[i]<Rank[j];25 else{26 int ri = i+k<=n?Rank[i+k]:-1;27 int rj = j+k<=n?Rank[j+k]:-1;28 return ri<rj;29 }30 }31 void construct_sa(string S,int *sa){32 n = S.length();33 //长度为1的字符串,Rank直接取字符的编码34 for(int i=0;i<=n;++i){35 sa[i]=i;36 Rank[i]=i<n?S[i]:-1;37 }38 //利用对长度为k的字符串排序计算长度位2k的顺序39 for(k=1;k<=n;k*=2){//注意这里不是 int k40 sort(sa,sa+n+1,cmp_sa);41 //计算新的rank，暂存到temp中42 temp[sa[0]]=0;43 //调整rank,相同的字符串的rank时一样的44 for(int i=1;i<=n;++i){45 temp[sa[i]] = temp[sa[i-1]]+ (cmp_sa(sa[i-1],sa[i])?1:0);46 }47 //存回rank48 for(int i=0;i<=n;++i){49 Rank[i]=temp[i];50 }51 }52 }53 //计算LCP，O（n）54 void construct_lcp(string S,int *sa,int *lcp){55 n = S.length();56 for(int i=0;i<=n;++i)Rank[sa[i]]=i;57 int h=0;58 lcp[0]=0;59 for(int i=0;i<n;++i){60 //计算字符串从i位置开始的后缀及其在后缀数组前一个的后缀的LCP61 int j = sa[Rank[i]-1];62 //将h先减去首字母的1的长度，保持前缀相同前提下不断增加63 if(h>0)h--;64 for(;j+h<n&&i+h<n;++h){65 if(S[j+h]!=S[i+h])break;66 }67 lcp[Rank[i]-1]=h;68 }69 }70 int main (){71 //freopen("in.txt","r",stdin);72 //freopen("out.txt","w",stdout);73 ios::sync_with_stdio(false);74 int t;75 string S;76 cin>>t;77 while(t--){78 cin>>S;79 int m = S.length();80 S+=S;81 construct_sa(S,SA);82 construct_lcp(S,SA,LCP);83 int N = 2*m;84 int pos =0;85 int ans;86 for(int i=0;i<=N;++i){87 if(SA[i]<m){88 pos =i;89 ans = SA[pos]+1;90 break;91 }92 }93 while(LCP[pos]>=m){94 pos++;95 ans = min(SA[pos]+1,ans);96 }97 cout<<ans<<endl;98 }99 }
poj 1509 Glass Beads
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。