网站换空间 seo,内江 网站建设,电子商务网站建设与维护教案,wordpress更换登录账号后缀数组SA
模板
花了不少时间才理解倍增求SASASA的实现方法#xff0c;我还是太菜了。
定义sa[i]sa[i]sa[i]表示排名为iii的后缀的起始位置。 定义rank[i]rank[i]rank[i]表示起始位置为iii的后缀的排名。 显然两者之前互逆。
void solve()
{int m122;for (int i1;im;…后缀数组SA
模板
花了不少时间才理解倍增求SASASA的实现方法我还是太菜了。
定义sa[i]sa[i]sa[i]表示排名为iii的后缀的起始位置。 定义rank[i]rank[i]rank[i]表示起始位置为iii的后缀的排名。 显然两者之前互逆。
void solve()
{int m122;for (int i1;im;i) cnt[i]0;for (int i1;in;i) cnt[x[i]a[i]];for (int i1;im;i) cnt[i]cnt[i-1];for (int in;i1;i--) sa[cnt[x[i]]--]i;for (int k1;kn;k1){int p0;for (int i1;im;i) y[i]0;for (int in-k1;in;i) y[p]i;for (int i1;in;i) if (sa[i]k) y[p]sa[i]-k;for (int i0;im;i) cnt[i]0;for (int i1;in;i) cnt[x[y[i]]];for (int i1;im;i) cnt[i]cnt[i-1];for (int in;i1;i--) sa[cnt[x[y[i]]]--]y[i];swap(x,y);x[sa[1]]p1;for (int i2;in;i)x[sa[i]](y[sa[i]]y[sa[i-1]]y[sa[i]k]y[sa[i-1]k])?p:p;if (pn) break;mp;}
}Height以及LCP
定义LCP(x,y)LCP(x,y)LCP(x,y)表示字符串xxx与yyy之间的最长公共前缀长度。
定义height[i]height[i]height[i]表示suffix[sa[i−1]]suffix[sa[i-1]]suffix[sa[i−1]]和suffix[sa[i]]suffix[sa[i]]suffix[sa[i]]的LCPLCPLCP的长度即相邻排名的后缀的LCPLCPLCP长度。
容易发现一个性质 对于任意的j,kj,kj,k若rank[j[rank[k]rank[j[rank[k]rank[j[rank[k]则suffix(j),suffix(k)suffix(j),suffix(k)suffix(j),suffix(k)的LCPLCPLCP的长度为 minirank[j]1rank[k]height[i]min_{irank[j]1}^{rank[k]}height[i] minirank[j]1rank[k]height[i] 即两个后缀j,kj,kj,k的LCPLCPLCP长度是排名在它们之间所有的后缀包括suffix(k)suffix(k)suffix(k)的heightheightheight值的最小值。
根据这一性质倘若我们可以求出height[i]height[i]height[i]我们就可以通过STSTST表O(nlgn)O(nlgn)O(nlgn)预处理O(1)O(1)O(1)询问两个后缀的LCPLCPLCP答案了。
而对于heightheightheight数组也有一个重要的性质 height[i−1]−1≤height[i]height[i-1]-1\leq height[i] height[i−1]−1≤height[i] 于是可以O(n)O(n)O(n)计算heightheightheight了。
void get_height()
{for (int i1;in;i) rnk[sa[i]]i;for (int i1,j0;in;i){if (j) j--;while (a[ij]a[sa[rnk[i]-1]j]) j;height[rnk[i]]j;}
}SA的简单应用
1.求最长重复子串
答案为heightheightheight最大值。
2.求最长重复k次子串
二分答案转化为判断是否存在长度为xxx的子串重复至少kkk次。将所有相邻且heightheightheight大于等于xxx的都分在一组判断是否有一组的后缀个数大于kkk即可。
时间复杂度O(n)O(n)O(n)
3.本质不同子串个数
答案为产生的新串数量-重复出现的串的数量。 则∑i(n−i1)−height[rnk[i]]\sum_{i} (n-i1)-height[rnk[i]]∑i(n−i1)−height[rnk[i]]。
