本文主要是介绍【蓝桥杯】算法提高 着急的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;
}
END
这篇关于【蓝桥杯】算法提高 着急的WYF（不同子串个数）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
