[关闭]
@xzyxzy 2018-07-02T10:15:58.000000Z 字数 4717 阅读 604

后缀数组(SA)

字符串

作业部落

评论地址


一、概述

一个可以对一个字符串的所有后缀处理的算法
网上优秀博客

二、题单

三、题解

[luogu3809]【模板】后缀排序
板子,求数组

[hihocoder1403] 后缀数组一·重复旋律
后单调队列求解至少出现次的最长子串

[hihocoder1407] 后缀数组二·重复旋律2
[hihocoder1415] 后缀数组三·重复旋律3
[POJ2774]Long Long Message
[Luogu2852][USACO06DEC]牛奶模式Milk Patterns
求两个字符串中的最长公共子串,把两串中间用一个从未出现过的字符连起来,跑后二分答案,如果有互不重叠且大于的那么返回

[BZOJ3238][AHOI2013]差异Hard
求串中任意两个子串的(最长公共前缀),利用性质,,所以维护一个单调递增栈,设表示栈中第个位置到个位置的所有贡献,通过可以算贡献

[Luogu2463][SDOI2008]Sandy的卡片
[BZOJ2946]公共串
求多串中的最长公共子串,将所有串连接成一个串,中间用一个从未出现过的字符隔开,那么后二分最长公共子串的长度,若数组中有连续的一段,且这一段中所有的子串都出现过,那么合法

[BZOJ1031]字符加密
把字符串,在按照数组输出符合条件的字符

[BZOJ4199][NOI2015]品酒大会Hard
求最长公共前缀长度为的后缀对数以及得分最大的一对的得分。
那么一段区间都大于等于,它会被都计算贡献,所以大的贡献不会影响小的贡献,把height排序之后从大到小处理,每处理一个就把两个串并起来,表示之后会一起处理,同时答案加上两个并查集的之积(两并查集内任意一对都符合条件),最大值便是两并查集最大值之积或最小值之积(负数)

[BZOJ4556][TJOI2016&&HEOI2016]字符串Hard
求一个串与一段区间内的串的最长前缀。
二分答案,那么符合答案的是上一段连续的区间,分别二分左右端点,现在就是判断上是否存在一个数在之间,转化为二维数点问题,用主席树完成

[luogu4143]采集矿石Hard
得到函数单调的性质后,考虑用后缀数组求一个子串的排名
其实一个后缀贡献的本质不同的字符串就是
1如果

2其他情况找到一个最大的使得那么套用上式
然后这题枚举二分下,判断与其权值是否相等即可

四、经验


多个字符不好处理的时候在中间依次添加从未出现过的字符(第一次加第二次加什么的),使得前后两个字符不会有的贡献


排好序后,二分一段区间使得以区间任意一个位置为开头的字符串与字符串(也在区间内)的最长前缀时,建议分别二分左右端点,而不是倍增地跳(调试2hTJOI2016字符串,因为不好选取倍增起点,ST表中任意一个数值都至少由两个字符串得来)

五、模板

洛谷3809后缀排序
记忆方式
Sort里面4行,预处理1行,倍增求SA枚举1行,中间5行
height2行枚举3行内容

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstdlib>
  4. #include<cstring>
  5. using namespace std;
  6. const int MAXN=2200000;
  7. char ch[MAXN];//字符串
  8. int m=1000;//字符集大小
  9. int s[MAXN],l,len1,len2;//字符串长度
  10. int SA[MAXN];//SA[i]表示排名为i的字符串是以SA[i]为开头的后缀
  11. int x[MAXN],y[MAXN];//记录两维信息方便排序
  12. int t[MAXN];//桶
  13. int Rank[MAXN];
  14. int height[MAXN];
  15. /*
  16. SA[i]=k 表示排名为i的是第k号串
  17. x[i]=k 表示i号串的第一关键字排名为k
  18. y[i]=k 表示第二关键字排名为i的是第k号串
  19. t[i]=k (统计前缀和之前)表示排名并列为i的串的数量是k
  20. (统计前缀和之后)表示排名为1~i的串的数量是k
  21. Rank[i]=k 表示第i号串的排名是k(与SA互逆)
  22. height[i]=k 表示lcp(Suffix(SA[i-1]),Suffix(SA[i]))
  23. 就是排名为i-1的串和排名为i的串的最长公共前缀
  24. */
  25. int cmp(int i,int j,int k)
  26. {
  27. return y[i]==y[j]&&y[i+k]==y[j+k];
  28. }
  29. void Sort()
  30. {
  31. for(int i=1;i<=m;i++) t[i]=0;
  32. for(int i=1;i<=l;i++) t[x[i]]++;
  33. for(int i=1;i<=m;i++) t[i]+=t[i-1];
  34. for(int i=l;i>=1;i--) SA[t[x[y[i]]]--]=y[i];//容易打反
  35. }
  36. void Get_SA()
  37. {
  38. for(int i=1;i<=l;i++) x[i]=s[i],y[i]=i; Sort();
  39. for(int k=1,p=0;k<=l;k<<=1)
  40. {
  41. for(int i=l-k+1;i<=l;i++) y[++p]=i;
  42. for(int i=1;i<=l;i++) if(SA[i]>k) y[++p]=SA[i]-k;
  43. Sort();swap(x,y);x[SA[1]]=p=1;
  44. for(int i=2;i<=l;i++) x[SA[i]]=cmp(SA[i],SA[i-1],k)?p:++p;//容易x中不写SA[i]
  45. if(p==l) break; m=p;p=0;
  46. //如果第一维已经有序,那么就不需要继续排序了~
  47. }
  48. /*
  49. for(int i=1;i<=l;i++) Rank[SA[i]]=i;
  50. for(int i=1,j=0;i<=l;i++)
  51. {
  52. if(j) j--; //利用性质:height[Rank[i]]>=height[Rank[i-1]]-1
  53. while(s[i+j]==s[SA[Rank[i]-1]+j]) j++;
  54. height[Rank[i]]=j;
  55. }
  56. */
  57. }
  58. int main()
  59. {
  60. scanf("%s",ch); int len=strlen(ch);
  61. for(int i=0;i<len;i++) s[++l]=ch[i];
  62. Get_SA();
  63. for(int i=1;i<=l;i++) printf("%d ",SA[i]);
  64. puts("");return 0;
  65. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注