【蓝桥杯】算法提高着急的WYF（不同子串个数）

本文主要是介绍【蓝桥杯】算法提高着急的WYF（不同子串个数），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

算法提高着急的WYF

问题描述

WYF在战网上的密码非常复杂（含大小写字母、数字以及特殊字符，如 ”!”,”@”,”{” 等），但他很不巧地忘记了。现在他非常着急，都快飞起来了。他只记得他的密码是某个字符串S的子串。现在问题来了，你要告诉他有多少种可能的密码，以帮助他确定能在多少时间内完成枚举并尝试解密工作。

输入格式

输入仅包含一行，为一个字符串S，不含空格。

输出格式

输出一个整数，表示可能的密码数量。

样例输入

ToTal

样例输出

14

数据规模和约定

对于70%的数据，S的长度不超过1000；（暴力）
对于100%的数据，S的长度不超过15000。（Suffix Array）

—— 分割线 ——

分析：

题目已经给了提示，想要过所有的测试数据，必须要用到Suffix Array（后缀数组）。

由于之前我已经详细地讲解了关于后缀数组的相关知识，并介绍了其在求字符串子串个数上的应用，因此这里我就不多说口水话了，直接上代码（如果有没看过那篇文章的同学，我强烈建议先看再做，这是链接【算法与数据结构】—— 后缀数组），本题的完整代码如下：

#include<iostream>
using namespace std;const int N=15010;
class SuffixArray{private:static const int MAX=N;int wa[MAX],wb[MAX],wd[MAX],r[MAX];			//n表示字符串的长度 bool isSame(int *r,int a,int b,int len){ return r[a]==r[b] && r[a+len]==r[b+len]; }void da(int n,int m)						 {int *x=wa,*y=wb,*t;for(int i=0;i<m;i++) wd[i]=0;for(int i=0;i<n;i++) wd[x[i]=r[i]]++;for(int i=1;i<m;i++) wd[i]+=wd[i-1];for(int i=n-1;i>=0;i--) sa[--wd[x[i]]]=i;for(int j=1,p=1;p<n;j<<1,m=p){//对第二关键字排序p=0;for(int i=n-j;i<n;i++) y[p++]=i;for(int i=0;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j;//对第一关键字排序for(int i=0;i<m;i++) wd[i]=0;for(int i=0;i<n;i++) wd[x[i]]++;for(int i=1;i<m;i++) wd[i]+=wd[i-1];for(int i=n-1;i>=0;i--) sa[--wd[x[y[i]]]]=y[i];//利用指针操作调换两数组的内容t=x,x=y,y=t;//更新x数组 p=1,x[sa[0]]=0;for(int i=1;i<n;i++) x[sa[i]]=isSame(y,sa[i-1],sa[i],j)?p-1:p++;}}public:int sa[MAX],rank[MAX],height[MAX],n; void calSuffixArray(char *s)		//计算后缀数组sa {n=0;while(*s){r[n++]=*s-'!'+1;s++;}r[n]=0; 						//对于r数组而言，其还需要在最后加一个0方便处理 da(n+1,100);					 }void calRank()						//计算名次数组rank {  for(int i=1;i<=n;i++) rank[sa[i]]=i;  }void calHeight()					//计算相邻的两个后缀的最长公共前缀长度数组height {int j,k=0;calRank();for(int i=0;i<n;i++){if(k) k--;int j=sa[rank[i]-1];while(r[i+k]==r[j+k]) k++;height[rank[i]]=k;}}long long calSubstringNum(char *s)	//对于某个字符串str，计算其不同子串的个数 {calSuffixArray(s);calHeight();long long ans=0;for(int i=1;i<=n;i++)ans += n - sa[i] -height[i];return ans;}
};int main()
{char chs[N];cin>>chs;SuffixArray suffixArray;cout<<suffixArray.calSubstringNum(chs)<<endl;return 0;
}