—————————————————————————————————————
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
struct SA { char s[N]; int cnta[N],sa[N],rank[N*2],a[N],b[N],cntb[N],tsa[N],height[N]; void Get_SA() { for (int i=0;i<=256;i++) cnta[i]=0; for (int i=1;i<=n;i++) cnta[s[i]]++; for (int i=1;i<=256;i++) cnta[i]+=cnta[i-1]; for (int i=n;i>=1;i--) sa[cnta[s[i]]--]=i; rank[sa[1]]=1; for (int i=2;i<=n;i++) rank[sa[i]]=rank[sa[i-1]]+(s[sa[i]]!=s[sa[i-1]]); for (int i=1;rank[sa[n]]!=n;i<<=1) { for (int j=1;j<=n;j++) a[j]=rank[j],b[j]=rank[j+i]; for (int j=0;j<=n;j++) cnta[j]=0,cntb[j]=0; for (int j=1;j<=n;j++) cnta[a[j]]++,cntb[b[j]]++; for (int j=1;j<=n;j++) cnta[j]+=cnta[j-1],cntb[j]+=cntb[j-1]; for (int j=n;j>=1;j--) tsa[cntb[b[j]]--]=j; for (int j=n;j>=1;j--) sa[cnta[a[tsa[j]]]--]=tsa[j]; rank[sa[1]]=1; for (int j=2;j<=n;j++) rank[sa[j]]=rank[sa[j-1]]+(a[sa[j]]!=a[sa[j-1]]||b[sa[j]]!=b[sa[j-1]]); } } void Get_Height() { int len=0; for (int i=1;i<=n;i++) { if (len) len--; while (s[i+len]==s[sa[rank[i]-1]+len]) len++; height[rank[i]]=len; } } }S; |
