倍增算法
<pre><code class="language-cpp">namespace suffix_array{
int sa[maxn], rak[maxn];
//sa[i] 排名为i的后缀的起始下标
//rak[i] 起始下标为i的后缀的排名
int cnt[maxn], pos[maxn];
int height[maxn];
void getHeight(const string &str, int n){
int k = 0;
for(int i = 1; i <= n; i++) rak[sa[i]] = i;
for(int i = 1; i <= n; i++){
if(rak[i] == 1) continue;
if(k) k--;
int j = sa[rak[i]-1];
while(j+k-1 < n && i+k-1 < n && str[i+k-1] == str[j+k-1]) k++;
height[rak[i]] = k;
}
return;
}
void getSA(const string &str, int n, int m = 130){//n为字符串长度
for(int i = 1; i <= m; i++) cnt[i] = 0;
for(int i = 1; i <= n; i++) cnt[rak[i] = str[i-1] - '\0']++;
for(int i = 1; i <= m; i++) cnt[i] += cnt[i-1];
for(int i = n; i >= 1; i--) sa[cnt[rak[i]]--] = i;
for(int k = 1, p = 0; p < n && k < n; k <<= 1, m = p, p = 0){
for(int i = n - k + 1; i <= n; i++) pos[++p] = i;
for(int i = 1; i <= n; i++){
if(sa[i] > k) pos[++p] = sa[i] - k;
}
for(int i = 0; i <= m; i++) cnt[i] = 0;
for(int i = 1; i <= n; i++) cnt[rak[i]]++;
for(int i = 1; i <= m; i++) cnt[i] += cnt[i-1];
for(int i = n; i >= 1; i--) sa[cnt[rak[pos[i]]]--] = pos[i];
for(int i = 1; i <= n; i++) pos[i] = rak[i];
p = 1; rak[sa[1]] = 1;
for(int i = 2; i <= n; i++){
if(pos[sa[i]] != pos[sa[i-1]] || pos[sa[i]+k] != pos[sa[i-1]+k]) p++;
rak[sa[i]] = p;
}
}
return;
}
}</code></pre>