后缀数组
一个后缀数组的板子。
感觉后缀数组的关键就是倍增思想以及二元组采用基数排序的 O ( n ) O(n) O(n)的神奇
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+5;
char str[N];
int n,sa[N],rk[N];
int tp[N],tax[N],*tmp;
void tuple_sort(const int N)
{
for(int i=0;i<N;++i) tax[i]=0;
for(int i=0;i<n;++i) tax[rk[i]]++;
for(int i=1;i<N;++i) tax[i]+=tax[i-1];
for(int i=n-1;i>=0;--i) sa[--tax[rk[tp[i]]]]=tp[i];
}
void solve()
{
scanf("%s",str);
n=strlen(str);
for(int i=0;i<n;++i) rk[i]=str[i], tp[i]=i;
tuple_sort(0xff);
for(int m=1;m<n;m<<=1)
{
int cnt=0;
for(int i=n-m;i<n;++i) tp[cnt++]=i;
for(int i=0;i<n;++i) if(sa[i]>=m) tp[cnt++]=sa[i]-m;
tuple_sort(cnt);
std::swap(rk,tp);
rk[sa[0]]=(cnt=0)++;
for(int i=1;i<n;++i) rk[sa[i]]=(tp[sa[i-1]]==tp[sa[i]] and tp[sa[i-1]+m]==tp[sa[i]+m])? cnt-1:cnt++;
}
for(int i=0;i<n;++i) printf("%d ",sa[i]+1);
printf("\n");
}
signed main()
{
int T=1;
for(int i=1;i<=T;i++)
{
solve();
}
return 0;
}
代码来自连接讲解也很好
P4051 [JSOI2007]字符加密
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+5;
char str[N];
int n,sa[N],rk[N];
int tp[N],tax[N],*tmp;
void tuple_sort(const int N)
{
for(int i=0;i<N;++i) tax[i]=0;
for(int i=0;i<n;++i) tax[rk[i]]++;
for(int i=1;i<N;++i) tax[i]+=tax[i-1];
for(int i=n-1;i>=0;--i) sa[--tax[rk[tp[i]]]]=tp[i];
}
void solve()
{
scanf("%s",str);
n=strlen(str);
for(int i=0;i<n;i++) str[i+n]=str[i];
n=n*2;
for(int i=0;i<n;++i) rk[i]=str[i], tp[i]=i;
tuple_sort(0xff);
for(int m=1;m<n;m<<=1)
{
int cnt=0;
for(int i=n-m;i<n;++i) tp[cnt++]=i;
for(int i=0;i<n;++i) if(sa[i]>=m) tp[cnt++]=sa[i]-m;
tuple_sort(cnt);
std::swap(rk,tp);
rk[sa[0]]=(cnt=0)++;
for(int i=1;i<n;++i) rk[sa[i]]=(tp[sa[i-1]]==tp[sa[i]] and tp[sa[i-1]+m]==tp[sa[i]+m])? cnt-1:cnt++;
}
for(int i=0;i<n;i++) if(sa[i]<n/2) printf("%c",str[sa[i]+n/2-1]);
}
signed main()
{
int T=1;
for(int i=1;i<=T;i++) solve();
return 0;
}
P2870 [USACO07DEC]Best Cow Line G
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+5;
char str[N];
int n,sa[N],rk[N];
int tp[N],tax[N],*tmp;
void tuple_sort(const int N)
{
for(int i=0;i<N;++i) tax[i]=0;
for(int i=0;i<n;++i) tax[rk[i]]++;
for(int i=1;i<N;++i) tax[i]+=tax[i-1];
for(int i=n-1;i>=0;--i) sa[--tax[rk[tp[i]]]]=tp[i];
}
void get_suffix()
{
for(int i=0;i<n;++i) rk[i]=str[i], tp[i]=i;
tuple_sort(0xff);
for(int m=1;m<n;m<<=1)
{
int cnt=0;
for(int i=n-m;i<n;++i) tp[cnt++]=i;
for(int i=0;i<n;++i) if(sa[i]>=m) tp[cnt++]=sa[i]-m;
tuple_sort(cnt);
std::swap(rk,tp);
rk[sa[0]]=(cnt=0)++;
for(int i=1;i<n;++i) rk[sa[i]]=(tp[sa[i-1]]==tp[sa[i]] and tp[sa[i-1]+m]==tp[sa[i]+m])? cnt-1:cnt++;
}
}
//int n;
void solve()
{
scanf("%d",&n);
for(int i=0;i<n;i++)scanf("%s",&str[i]);
str[n]='A'-1;
for(int i=0;i<n;i++) str[i+n+1]=str[n-1-i];
n=n*2+1;
// for(int i=0;i<n;i++)cout<<str[i];
// cout<<endl;
get_suffix();
int l=0,r=((n-1)>>1)-1,cnt=0;
// cout<<r<<endl;
while(l<=r)
{
// cout<<rk[l]<<" "<<rk[n-r-1]<<endl;
printf("%c",rk[l]<rk[n-r-1]?str[l++]:str[r--]);
if(++cnt%80==0)puts("");
}
}
signed main()
{
int T=1;
for(int i=1;i<=T;i++) solve();
return 0;
}
习题集
Uva 760 - DNA Sequencing
Uva 1223 - Editor
Codechef - Tandem
Codechef - Substrings and Repetitions
Codechef - Entangled Strings
Codeforces - Martian Strings
Codeforces - Little Elephant and Strings
SPOJ - Ada and Terramorphing
SPOJ - Ada and Substring
UVA - 1227 - The longest constant gene
SPOJ - Longest Common Substring
UVA 11512 - GATTACA
LA 7502 - Suffixes and Palindromes
GYM - Por Costel and the Censorship Committee
UVA 1254 - Top 10
UVA 12191 - File Recover
UVA 12206 - Stammering Aliens
Codechef - Jarvis and LCP
LA 3943 - Liking’s Letter
UVA 11107 - Life Forms
UVA 12974 - Exquisite Strings
UVA 10526 - Intellectual Property
UVA 12338 - Anti-Rhyme Pairs
DevSkills Reconstructing Blue Print of Life
UVA 12191 - File Recover
SPOJ - Suffix Array
LA 4513 - Stammering Aliens
SPOJ - LCS2
Codeforces - Fake News (hard)
SPOJ - Longest Commong Substring
SPOJ - Lexicographical Substring Search
Codeforces - Forbidden Indices
Codeforces - Tricky and Clever Password
LA 6856 - Circle of digits
