SA后缀数组
【模板】后缀数组
理解全在代码里
定义 ：
$sa[i]$ 表示排名为i的后缀的开头位置
$rk[i]$ 表示以i为开头的后缀的排名（这里$i$均表示下标）
$tmp[i]$ 表示i对应的i-w的位置，为后面倍增两两合并准备
$height[i]$ 表示$lcp{({sa[i]},{sa[i - 1]})}$
$cnt[i]$ 计数排序的计数器
void get_sa(){int m = 255 ;for(int i = 1 ; i <= n ;++i)cnt[rnk[i] = s[i]]++; //初始化，给长度为1的赋值for(int i = 1 ; i <= m ;++i)cnt[i] += cnt[i - 1] ;//前缀和，计算for(int i = n ; i >= 1 ;--i)sa[cnt[rnk[i]]--] = i ; for(int w = 1 , t = 0 ; ; m = t , t = 0 , w <<= 1 ){//每次倍增长度for(int i = n - w + 1 ; i <= n ;++i)tmp[++t] = i;//如果 i + w > 0 就把他平行移到左边for(int i = 1 ; i <= n ;++i)if( sa[i] > w )tmp[++t] = sa[i] - w ;//否则直接赋值// for(int i = 1 ; i <= n ; i++){// cout << i << " " << tmp[i] << " " << w << endl ; // } // cout << endl ; for(int i = 0 ; i <= m ;++i)cnt[i] = 0 ;//重置计数器for(int i = 1 ; i <= n ;++i)cnt[rnk[tmp[i]]]++;//对第一关键字进行计数排序for(int i = 1 ; i <= m ;++i)cnt[i] += cnt[i - 1];//前缀和for(int i = n ; i >= 1 ;--i)sa[cnt[rnk[tmp[i]]]--]= tmp[i];//计算sa swap(rnk , tmp) , t = 0 ;//这里应该是节省空间 直接使用把老的rnk赋给tmp , 用老的rnk更新新的rnkfor(int i = 1 ; i <= n ; i++)rnk[sa[i]] = (tmp[sa[i]] == tmp[sa[i - 1]] and tmp[sa[i] + w] == tmp[sa[i - 1] + w] ) ? t : ++t ; if( t == n )break ;//如果已经够了就不再排序了}
}
void getHeight(){for(int i = 1 , k = 0 ; i <= n ; ++i){if(k)--k;while(s[i + k] == s[sa[rnk[i] - 1] + k])k++;//直接暴力扩展height[rnk[i]] = k ;}
}
getHeight函数复杂度均摊$O(n)$
get_sa函数复杂度$O(n{logn})$
应用：
1.比较两个子串的大小关系
2.不同子串的数目
不同子串个数有 ：$\{n*(n+1)/2 + sum_{i=1}height[i]}$ 种