题意：
给一个长度为n的字符串s[0..n-1]，但i的后继不再是i+1，而是(i*i+1)%n，求所有长度为n的“子串”中，字典序最大的是谁
n<=150000,s[i]=0..9
思路：后缀数组
因为前驱与后继的关系已经变化，就不能用下标直接加减
i的后继是唯一的，i的前驱却不一定
所以对于后继使用倍增，对于前驱每个位置暴力开队列存储，需要的时候再拿出来
在判断的地方稍作修改
1 #include<cstdio> 2 #include<cstring> 3 #include<string> 4 #include<cmath> 5 #include<iostream> 6 #include<algorithm> 7 #include<map> 8 #include<set> 9 #include<queue> 10 #include<vector> 11 #include<bits/stdc++.h> 12 using namespace std; 13 typedef long long ll; 14 typedef unsigned int uint; 15 typedef unsigned long long ull; 16 typedef pair<int,int> PII; 17 typedef vector<int> VI; 18 #define fi first 19 #define se second 20 #define MP make_pair 21 #define N 310000 22 #define MOD 1000000007 23 #define eps 1e-8 24 #define pi acos(-1) 25 queue<int> q[N]; 26 27 char ch[N]; 28 int n,s[N],sa[N],wa[N],wb[N],wc[N],wd[N],height[N],Rank[N], 29 f[N][19]; 30 31 32 int read() 33 { 34 int v=0,f=1; 35 char c=getchar(); 36 while(c<48||57<c) {if(c=='-') f=-1; c=getchar();} 37 while(48<=c&&c<=57) v=(v<<3)+v+v+c-48,c=getchar(); 38 return v*f; 39 } 40 41 bool cmp(int *r,int a,int b,int l) 42 { 43 return r[a]==r[b]&&r[f[a][l]]==r[f[b][l]]; 44 // return r[a]==r[b]&&r[a+l]==r[b+l]; 原来的写法 45 } 46 47 void getsa(int *r,int *sa,int n,int m) 48 { 49 // printf(" "); 50 int *x=wa,*y=wb,p; 51 int k=0; 52 for(int i=0;i<n;i++) wc[x[i]=r[i]]++; 53 for(int i=1;i<m;i++) wc[i]+=wc[i-1]; 54 for(int i=n-1;i>=0;i--) sa[--wc[x[i]]]=i; 55 for(int j=1,p=1;p<n;j*=2,m=p) 56 { 57 p=0; 58 /*for(i=n-j;i<n;i++) y[p++]=i; 59 for(i=0;i<n;i++) 60 if(sa[i]>=j) y[p++]=sa[i]-j; 61 */ //默认后继为i+1应该是这个写法 62 63 for(int i=0;i<n;i++) q[f[i][k]].push(i); 64 for(int i=0;i<n;i++) 65 while(!q[sa[i]].empty()) 66 { 67 y[p++]=q[sa[i]].front(); 68 q[sa[i]].pop(); 69 } 70 for(int i=0;i<n;i++) wd[i]=x[y[i]]; 71 for(int i=0;i<m;i++) wc[i]=0; 72 for(int i=0;i<n;i++) wc[wd[i]]++; 73 for(int i=1;i<m;i++) wc[i]+=wc[i-1]; 74 for(int i=n-1;i>=0;i--) sa[--wc[wd[i]]]=y[i]; 75 swap(x,y); 76 p=1; x[sa[0]]=0; 77 for(int i=1;i<n;i++) 78 x[sa[i]]=cmp(y,sa[i-1],sa[i],k)?p-1:p++; 79 //printf("%d %d %d ",k,j,p); 80 k++; 81 if(j>n) break; //加上这句就A了，应该都是N很大，D[i]相同的数据吧，名次的并列很多 82 } 83 } 84 85 86 87 int main() 88 { 89 freopen("hdoj6223.in","r",stdin); 90 freopen("hdoj6223.out","w",stdout); 91 int cas; 92 scanf("%d",&cas); 93 for(int v=1;v<=cas;v++) 94 { 95 printf("Case #%d: ",v); 96 scanf("%d",&n); 97 scanf("%s",ch); 98 for(int i=0;i<n;i++) s[i]=ch[i]-'0'+1; 99 for(int i=0;i<n;i++) f[i][0]=(1LL*i*i+1)%n; 100 101 for(int j=1;j<=18;j++) 102 for(int i=0;i<n;i++) f[i][j]=f[f[i][j-1]][j-1]; 103 104 105 106 s[n]=0; 107 getsa(s,sa,n+1,20); 108 int k=sa[n]; 109 for(int i=1;i<=n;i++) 110 { 111 printf("%c",ch[k]); 112 k=f[k][0]; 113 } 114 printf(" "); 115 for(int i=0;i<=max(20,n);i++) 116 { 117 s[i]=sa[i]=wa[i]=wb[i]=wc[i]=wd[i]= 118 Rank[i]=0; 119 } 120 } 121 return 0; 122 } 123