• 【字符串】后缀数组

     参考文章：

    数据结构 —— 字符串：后缀数组_Jetiaime的博客-CSDN博客（算法代码）

    后缀数组_KonjakLAF的博客-CSDN博客（应用+例题）

    板子：

    1. #include
    2. using namespace std;
    3. typedef long long ll;
    4. const int N=1e7+5;
    5. const int inf=1<<30;
    6. const ll INF=0x3f3f3f3f3f3f3f3f;
    7. int n,k;
    8. char s[N];
    9. int m,sa[N],cnt[N],rk[N],id[N],px[N],oldrk[N];
    10.  
    11. inline bool cmp(int x,int y,int k){
    12. 	return oldrk[x]==oldrk[y]&&oldrk[x+k]==oldrk[y+k];
    13. }
    14. inline void getsa(){
    15. 	//初始化 
    16. 	m=10;
    17. 	for(int i=1;i<=n;i++)cnt[rk[i]=s[i]-'0']++;
    18. 	for(int i=1;i<=m;i++)cnt[i]+=cnt[i-1];
    19. 	//for(int i=1;i<=9;i++)printf("cnt[%d]:%d\n",i,cnt[i]);
    20. 	for(int i=n;i;i--)sa[cnt[rk[i]]--]=i;
    21. 	//for(int i=1;i<=n;i++)printf("sa[%d]:%d %s\n",i,sa[i],s+sa[i]); 
    22. 	//倍增
    23. 	for(int k=1;k<=n;k<<=1){//后缀长度 
    24. 		int idx=0;
    25. 		for(int i=n;n-i
    26. 		for(int i=1;i<=n;i++)if(sa[i]>k)id[++idx]=sa[i]-k;//按后一半排序的后缀
    27. 		memset(cnt,0,sizeof(cnt));
    28. 		for(int i=1;i<=n;i++)cnt[px[i]=rk[id[i]]]++;
    29. 		for(int i=1;i<=m;i++)cnt[i]+=cnt[i-1];
    30. 		for(int i=n;i;i--)sa[cnt[px[i]]--]=id[i];
    31. 		idx=0;swap(oldrk,rk);
    32. 		for(int i=1;i<=n;i++)rk[sa[i]]=cmp(sa[i],sa[i-1],k)?idx:++idx;
    33. 		m=idx;
    34.         if(n==m)break;
    35. 		//for(int i=1;i<=n;i++)printf("sa[%d]:%d %s\n",i,sa[i],s+sa[i]); 
    36. 	}//for(int i=1;i<=n;i++)printf("sa[%d]:%d %s\n",i,sa[i],s+sa[i]); 
    37. }
    38. int val[N],len;
    39. inline void add(ll x){
    40. 	ll pre=x;
    41. 	for(int i=1;i<=len;i++){
    42. 		if(!pre)break;
    43. 		val[i]+=pre;
    44. 		pre=val[i]/10;
    45. 		val[i]%=10;
    46. 	}while(pre)val[++len]=pre%10,pre/=10;
    47. }
    48. int main(){
    49. 	scanf("%d%d",&n,&k);
    50. 	scanf("%s",s+1);
    51. 	getsa();
    52. 	ll res=0;len=n-k;
    53. 	for(int i=n;i;i--){
    54. 		if(sa[i]<=k+1){//sa[i]--sa[i]+n-k
    55. 			//printf("sa[%d]:%d %s\n",i,sa[i],s+sa[i]); 
    56. 			for(int j=sa[i],anj=len;j<=sa[i]+n-k-1;j++,anj--){
    57. 				//printf("s[%d]:%c %d\n",j,s[j],s[j]-'0');
    58. 				//res=res*10+int(s[j]-'0');
    59. 				val[anj]=s[j]-'0';
    60. 			}
    61. 			for(int j=1;j'0';
    62. 			for(int j=sa[i]+n-k;j<=n;j++)res+=s[j]-'0';
    63. 			//printf("%lld",res);
    64. 			add(res);
    65. 			for(int i=len;i;i--)printf("%d",val[i]);
    66. 			break;
    67. 		}
    68. 	}
    69. 	return 0;
    70. }

    例题： 

    例1：P3809 【模板】后缀排序 - 洛谷 (luogu.com.cn) 

    1. #include
    2. using namespace std;
    3. typedef long long ll;
    4. const int N=1e6+5;
    5. const int inf=1<<30;
    6. const ll INF=0x3f3f3f3f3f3f3f3f;
    7. char s[N];
    8. int l1,l2,n;
    9. int idx,m,sa[N],rk[N],oldrk[N],px[N],id[N],c[N];
    10. bool cmp(int x,int y,int k){
    11. 	return oldrk[x]==oldrk[y]&&oldrk[x+k]==oldrk[y+k];
    12. }
    13. void getsa(){
    14. 	//初始化
    15. 	m=150;
    16. 	for(int i=1;i<=n;i++)c[rk[i]=s[i]]++;
    17. 	for(int i=1;i<=m;i++)c[i]+=c[i-1];
    18. 	//for(int i=1;i<=m;i++)printf("c[%d]%d\n",i,c[i]);
    19. 	for(int i=n;i;i--)sa[c[rk[i]]--]=i;
    20. 	//for(int i=1;i<=n;i++)printf("sa[%d]%d %s\n",i,sa[i],s+sa[i]);
    21. 	//倍增
    22. 	for(int k=1;k<=n;k<<=1){
    23. 		idx=0;
    24. 		for(int i=n;n-i
    25. 		for(int i=1;i<=n;i++)if(sa[i]>k)id[++idx]=sa[i]-k;
    26. 		memset(c,0,sizeof(c));
    27. 		for(int i=1;i<=n;i++)c[px[i]=rk[id[i]]]++;
    28. 		for(int i=1;i<=m;i++)c[i]+=c[i-1];
    29. 		for(int i=n;i;i--)sa[c[px[i]]--]=id[i];
    30. 		swap(rk,oldrk);
    31. 		idx=0;
    32. 		for(int i=1;i<=n;i++)rk[sa[i]]=cmp(sa[i],sa[i-1],k)?idx:++idx;
    33.         if(idx==n)break;
    34. 		m=idx;
    35. 		//for(int i=1;i<=n;i++)printf("sa[%d]%d %s\n",i,sa[i],s+sa[i]);
    36. 	} 
    37. }
    38. int ht[N];
    39. void geth(){
    40. 	for(int i=1,k=0;i<=n;i++){
    41. 		if(k)k--;
    42. 		while(s[i+k]==s[sa[rk[i]-1]+k])k++;
    43. 		ht[rk[i]]=k;
    44. 	}
    45. }
    46.  
    47. inline void read(int &x){
    48. 	int f=1;
    49. 	x=0;
    50. 	char ch=getchar();
    51. 	while(ch<'0'||'9'
    52. 		if(ch=='-')f=-1;
    53. 		ch=getchar();
    54. 	}while('0'<=ch&&ch<='9'){
    55. 		x=(x<<3)+(x<<1)+(ch&15);
    56. 		ch=getchar();
    57. 	}x*=f;
    58. }
    59. inline void write(int x){
    60. 	if(x<0){
    61. 		putchar('-');x=-x;
    62. 	}if(x>9)write(x/10);
    63. 	putchar('0'+x%10);
    64. }
    65. int main(){
    66. 	scanf("%s",s+1);
    67. 	n=strlen(s+1);
    68.  
    69. 	getsa();geth();
    70. 	for(int i=1;i<=n;i++)printf("%d ",sa[i]);
    71. 	
    72. 	return 0;
    73. }

    例2：数字串 -matiji 

    题解：找到最大的n-k位数

    eg. 6 2 121312

    1. 样例：
    2. 6 2
    3. 121312
    4. 排序后：
    5. 12
    6. 121312
    7. 1312
    8. 2
    9. 21312
    10. 312

    倒序遍历找到最大的n-k位数

    注意：*1.由于字符串长度最大1e6，会爆ll，所以存储每一位的数字然后输出

               *2.getsa()函数中没有 if(n==m)break; 会超时

    1. #include
    2. using namespace std;
    3. typedef long long ll;
    4. const int N=1e7+5;
    5. const int inf=1<<30;
    6. const ll INF=0x3f3f3f3f3f3f3f3f;
    7. int n,k;
    8. char s[N];
    9. int m,sa[N],cnt[N],rk[N],id[N],px[N],oldrk[N];
    10.  
    11. inline bool cmp(int x,int y,int k){
    12. 	return oldrk[x]==oldrk[y]&&oldrk[x+k]==oldrk[y+k];
    13. }
    14. inline void getsa(){
    15. 	//初始化 
    16. 	m=10;
    17. 	for(int i=1;i<=n;i++)cnt[rk[i]=s[i]-'0']++;
    18. 	for(int i=1;i<=m;i++)cnt[i]+=cnt[i-1];
    19. 	//for(int i=1;i<=9;i++)printf("cnt[%d]:%d\n",i,cnt[i]);
    20. 	for(int i=n;i;i--)sa[cnt[rk[i]]--]=i;
    21. 	//for(int i=1;i<=n;i++)printf("sa[%d]:%d %s\n",i,sa[i],s+sa[i]); 
    22. 	//倍增
    23. 	for(int k=1;k<=n;k<<=1){//后缀长度 
    24. 		int idx=0;
    25. 		for(int i=n;n-i
    26. 		for(int i=1;i<=n;i++)if(sa[i]>k)id[++idx]=sa[i]-k;//按后一半排序的后缀
    27. 		memset(cnt,0,sizeof(cnt));
    28. 		for(int i=1;i<=n;i++)cnt[px[i]=rk[id[i]]]++;
    29. 		for(int i=1;i<=m;i++)cnt[i]+=cnt[i-1];
    30. 		for(int i=n;i;i--)sa[cnt[px[i]]--]=id[i];
    31. 		idx=0;swap(oldrk,rk);
    32. 		for(int i=1;i<=n;i++)rk[sa[i]]=cmp(sa[i],sa[i-1],k)?idx:++idx;
    33. 		m=idx;
    34.         if(n==m)break;
    35. 		//for(int i=1;i<=n;i++)printf("sa[%d]:%d %s\n",i,sa[i],s+sa[i]); 
    36. 	}//for(int i=1;i<=n;i++)printf("sa[%d]:%d %s\n",i,sa[i],s+sa[i]); 
    37. }
    38. int val[N],len;
    39. inline void add(ll x){
    40. 	ll pre=x;
    41. 	for(int i=1;i<=len;i++){
    42. 		if(!pre)break;
    43. 		val[i]+=pre;
    44. 		pre=val[i]/10;
    45. 		val[i]%=10;
    46. 	}while(pre)val[++len]=pre%10,pre/=10;
    47. }
    48. int main(){
    49. 	scanf("%d%d",&n,&k);
    50. 	scanf("%s",s+1);
    51. 	getsa();
    52. 	ll res=0;len=n-k;
    53. 	for(int i=n;i;i--){
    54. 		if(sa[i]<=k+1){//sa[i]--sa[i]+n-k
    55. 			//printf("sa[%d]:%d %s\n",i,sa[i],s+sa[i]); 
    56. 			for(int j=sa[i],anj=len;j<=sa[i]+n-k-1;j++,anj--){
    57. 				//printf("s[%d]:%c %d\n",j,s[j],s[j]-'0');
    58. 				//res=res*10+int(s[j]-'0');
    59. 				val[anj]=s[j]-'0';
    60. 			}
    61. 			for(int j=1;j'0';
    62. 			for(int j=sa[i]+n-k;j<=n;j++)res+=s[j]-'0';
    63. 			//printf("%lld",res);
    64. 			add(res);
    65. 			for(int i=len;i;i--)printf("%d",val[i]);
    66. 			break;
    67. 		}
    68. 	}
    69. 	return 0;
    70. }

    例3：乐曲主题 - 洛谷 （最长不重叠公共子串）

    转调后仍相同则差值相同，此时只需找不重叠的最长公共子串

    可转化为不同后缀的最长公共前缀，且不同后缀的公共前缀不重叠 

    后缀数组计算时cnt[a[i]]计数，而差值a[i]可能为负数如 1-88，在此给每一个a[i]+90 

    有子串长度为 4 时 "主题" 长度为 5 

    二分答案，答案变成判定性问题。

    将 height [ i ]分为连续的组，如果有连续的一段 height≥mid ，且 max(sai)−min(sai)>mid

    说明存在长度为 mid且不重叠的重复子串。

    *对 height [ i ] 分组的方法很重要。

    1. #include
    2. using namespace std;
    3. typedef long long ll;
    4. const int N=5e3+5;
    5. const int inf=1<<30;
    6. const ll INF=0x3f3f3f3f3f3f3f3f;
    7.  
    8. inline void read(ll &x){
    9. 	ll f=1;
    10. 	x=0;
    11. 	char ch=getchar();
    12. 	while(ch<'0'||'9'
    13. 		if(ch=='-')f=-1;
    14. 		ch=getchar();
    15. 	}while('0'<=ch&&ch<='9'){
    16. 		x=(x<<3)+(x<<1)+(ch&15);
    17. 		ch=getchar();
    18. 	}x*=f;
    19. }
    20. inline void write(int x){
    21. 	if(x<0){
    22. 		putchar('-');x=-x;
    23. 	}if(x>9)write(x/10);
    24. 	putchar('0'+x%10);
    25. }
    26. int n,a[N];
    27. int m,sa[N],rk[N],oldrk[N],px[N],id[N],idx,ht[N],c[N];
    28. bool cmp(int x,int y,int k){
    29. 	return oldrk[x]==oldrk[y]&&oldrk[x+k]==oldrk[y+k];
    30. }
    31. void getsa(){
    32. 	//初始化 
    33. 	m=180;
    34. 	for(int i=1;i<=n;i++)c[rk[i]=a[i]]++;
    35. 	for(int i=2;i<=m;i++)c[i]+=c[i-1];
    36. 	for(int i=n;i;i--)sa[c[rk[i]]--]=i;
    37. 	//倍增
    38. 	for(int k=1;k<=n;k<<=1){
    39. 		idx=0;
    40. 		for(int i=n;n-i
    41. 		for(int i=1;i<=n;i++)if(sa[i]>k)id[++idx]=sa[i]-k;
    42. 		memset(c,0,sizeof(c));
    43. 		for(int i=1;i<=n;i++)c[px[i]=rk[id[i]]]++;
    44. 		for(int i=2;i<=m;i++)c[i]+=c[i-1];
    45. 		for(int i=n;i;i--)sa[c[px[i]]--]=id[i];
    46. 		//更新rk 
    47. 		swap(rk,oldrk);idx=0;
    48. 		for(int i=1;i<=n;i++)rk[sa[i]]=cmp(sa[i],sa[i-1],k)?idx:++idx;
    49. 		if(idx==n)break;
    50. 		m=idx;
    51. 	} 
    52. }
    53. void geth(){
    54. 	for(int i=1,k=0;i<=n;i++){
    55. 		if(k)k--;
    56. 		while(a[i+k]==a[sa[rk[i]-1]+k])k++;
    57. 		ht[rk[i]]=k;
    58. 	}
    59. }
    60. int chk(int x){
    61. 	int mn=sa[1],mx=sa[1];
    62. 	for(int i=2;i<=n;i++){
    63. 		if(ht[i]
    64. 			mn=mx=sa[i];
    65. 		}else {
    66. 			mn=min(mn,sa[i]);
    67. 			mx=max(mx,sa[i]);
    68. 			if(mx-mn>x)return 1;
    69. 		}
    70. 	}return 0;
    71. }
    72. /*
    73. a 0
    74. aabcdd 1
    75. aabckm 4
    76. aabcko 5
    77. bac 0
    78. 此时ht为1 4 5的是一组 sa[i]max-sa[i]min+1 >= mid则不重复    
    79. */
    80. int main(){
    81. 	scanf("%d",&n);
    82. 	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    83. 	for(int i=1;i1]-a[i]+90;
    84. 	a[n--]=0;
    85. 	/*
    86. 		转调后仍相同则差值相同，此时只需找不重叠的最长公共子串
    87. 		可转化为不同后缀的最长公共前缀，且不同后缀的公共前缀不重叠 
    88. 		后缀数组计算时cnt[a[i]]计数，而差值a[i]可能为负数如 1-88，在此给每一个a[i]+90 
    89. 		有子串长度为 4 时 "主题" 长度为 5 
    90. 	*/
    91. 	getsa();geth();
    92. 	/* 二分查找最长长度 -> 转化为判定问题 */
    93. 	//for(int i=1;i<=n;i++)printf("a[%d]%d\n",i,a[i]);printf("\n");
    94. 	
    95. 	//for(int i=1;i
    96. 	int l=0,r=n,res=0;
    97. 	while(l<=r){
    98. 		int mid=(l+r)/2;
    99. 		if(chk(mid))res=mid,l=mid+1;
    100. 		else r=mid-1;//printf("l%d r%d res%d\n",l,r,res);
    101. 	}
    102. 	printf("%d",res>=4?res+1:0);
    103. 	return 0;
    104. }


     

  • 相关阅读:
    arc 166 a
    软件测试/测试开发丨Python安装指南（macOS）
    BUG：阿里巴巴图标库引入链接后，icon有时候会不显示的话svg下载到本地使用
    yarn安装及使用
    一.node的文件系统；二.node的数据流(Stream接口)；
    华为OD机试真题【篮球比赛】
    在Vue中使用Immutable.js
    计算机毕业设计ssm+vue基本微信小程序的心理服务平台
    z—libirary最新地址获取，zlibirary地址获取方式,zliabary最新地址,zliabary官网登录方式,zliabary最新登陆
    Java编码与解码
  • 原文地址：https://blog.csdn.net/m0_63851154/article/details/133087866