原题链接P5341 [TJOI2019]甲苯先生和大中锋的字符串
题目描述
大中锋有一个长度为 n 的字符串，他只知道其中的一个子串是祖上传下来的宝藏的密码。但是由于字符串很长，大中锋很难将这些子串一一尝试。
这天大中锋找到甲苯先生算命，但是甲苯先生说：“天机不可泄漏”。
在大中锋的苦苦哀求下，甲苯先生告诉大中锋：“密码是在字符串中恰好出现了 kk 次的子串”。
但是大中锋不知道该怎么做，在大中锋再三的恳求下，甲苯先生看其真诚，又告诉他：“在恰好出现了 k 次的子串中，你去按照字串的长度分类，密码就在数量最多的那一类里”。
大中锋为了尝试这个密码，想让你帮忙找出子串长度出现次数最多的长度数（如果有多个输出最长长度）。
输入输出格式
输入格式：
第一行一个正整数 T ，表示有 T 组测试数据。
接下来 T 行每行包含一个字符串和一个正整数 k 。
输出格式：
一共输出 T 行，每行一个整数表示在出现 k 次的子串中出现次数的最多的长度。如果不存在子串出现 k 次，则输出 −1 。
输入输出样例
说明
数据说明
对于第一个数据：其中子串 b,aa,ab,aab 均只出现一次，其中长度为 1 的子串现了 1 次，长度为 2 的子串出现了 2 次，长度为 3 的子串出现了 1 次。所以答案为 2 。
对于第二个数据：其中子串 a, b, c, ab, bc, abc 均只出现一次，其中长度为 1 的子串出现了 3 次，长度为 2 的子串出现了 2 次，长度为 3 的子串出现了 1 次。所以答案为 1 。
对于第三个数据：其中子串 aaa 出现二次，长度为 3 的子串出现了 1 次，其他长度均没有。所以答案为 3 。
对于第四个数据：其中子串 a, b, ab 出现二次，其中长度为 1 的子串出现了 2 次，长度为 2 的子串出现了 1次。所以答案为 1 。
对于第五个数据：其中子串 b, c, ab, ba 出现二次，其中长度为 1 的子串出现了 2 次，长度为 2 的子串出现了 2次。所以答案为 2 。
对于第六个数据：其中子串没有出现四次。所以本题的本题的答案为 −1 。
数据范围
对于 20% 的数据， 1≤k≤n≤10
对于 100% 的数据， 1≤n≤105,1≤T≤100,∑n≤3∗106 ，输入的字符串中仅包含小写英文字母。
题解
题意概括：给定一个字符串和整数k，求在其中出现次数为k的子串中数量最多的长度
（如果长度为i的出现为k次的子串有ans个，且任意j<i满足长度为j的出现次数为k的子串数量≤ans，j>i则<ans）
算法：统计子串（数量）问题，很容易想到后缀自动机SAM，后缀数组SA
此处介绍SAM的做法，实现很简单，代码接近于模板
实现：
1.初始化，按照原字符串建立SAM，建立后缀树，递归统计子串数量siz
2.核心代码：统计每一种长度的出现次数为k的子串的数量（“子串的数量”为不同子串的种类数）
定义ans数组，ans[i]表示长度为i的出现次数为k的子串的数量，ans[x]max=ans[i]则i即为所求
如何求ans数组？
对于每个状态，如果它的siz（代表的子串的出现次数）为k，则其代表的所有子串为所求，故可按长度统计入ans
那状态i代表的子串的长度又几何？
根据后缀自动机的性质，令len[i]为状态i表示的最长的子串str[i]的长度，则
①状态i表示的所有子串为str[i]连续的后缀
②状态i的后缀连接指向的状态link[i]表示的所有子串为str[i]的后缀
③len[link[i]]+1等于i表示的最短的子串的长度
所以状态i对ans的贡献即为对于x|len[link[i]]+1≤x≤len[i]，ans[x]++;
故可设ans为前缀和数组，将ans[len[link[i]]+1]++，ans[len[i]+1]--；
以下代码可在递归时操作，亦可另起一个循环
if(x&&siz[x]==K){ ans[len[link[x]]+1]++; ans[len[x]+1]--; }
完整代码：
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long LL; 4 const int INF=1e9+7,MAXN=2e5+7,MAXC=26; 5 int nxt[MAXN][MAXC],link[MAXN],len[MAXN],lst,sz,siz[MAXN]; 6 inline void extend(int c){ 7 int cur=++sz,p=lst; 8 len[cur]=len[p]+1; 9 siz[cur]=1; 10 while(p!=-1&&!nxt[p][c]){ 11 nxt[p][c]=cur; 12 p=link[p]; 13 } 14 if(p==-1) 15 link[cur]=0; 16 else{ 17 int q=nxt[p][c]; 18 if(len[q]==len[p]+1) 19 link[cur]=q; 20 else{ 21 int clone=++sz; 22 len[clone]=len[p]+1; 23 memcpy(nxt[clone],nxt[q],sizeof(nxt[clone])); 24 link[clone]=link[q]; 25 while(p!=-1&&nxt[p][c]==q){ 26 nxt[p][c]=clone; 27 p=link[p]; 28 } 29 link[q]=link[cur]=clone; 30 } 31 } 32 lst=cur; 33 } 34 int tp,head[MAXN],to[MAXN],nxt_[MAXN]; 35 inline void add(int x,int y){ 36 nxt_[++tp]=head[x]; 37 head[x]=tp; 38 to[tp]=y; 39 } 40 int K,ans[MAXN]; 41 void dfs(int x){ 42 for(int i=head[x];i;i=nxt_[i]){ 43 dfs(to[i]); 44 siz[x]+=siz[to[i]]; 45 } 46 if(x&&siz[x]==K){ 47 ans[len[link[x]]+1]++; 48 ans[len[x]+1]--; 49 } 50 } 51 char str[MAXN]; 52 int M; 53 int Case; 54 int main(){ 55 scanf("%d",&Case); 56 while(Case--){ 57 lst=sz=tp=0; 58 link[0]=-1; 59 scanf("%s%d",str+1,&K); 60 M=strlen(str+1); 61 for(int i=1;i<=M;i++) 62 extend(str[i]-'a'),siz[lst]=1; 63 for(int i=1;i<=sz;i++) 64 add(link[i],i); 65 dfs(0); 66 for(int i=1;i<=M;i++) 67 ans[i]+=ans[i-1]; 68 int maxi=0; 69 for(int i=M;i>=1;i--) 70 if(ans[i]>ans[maxi]) 71 maxi=i; 72 printf("%d ",maxi?maxi:-1); 73 for(int i=0;i<=sz;i++){ 74 len[i]=siz[i]=link[i]=0; 75 } 76 memset(head,0,sizeof(head)); 77 memset(ans,0,sizeof(ans)); 78 memset(nxt,0,sizeof(nxt)); 79 } 80 return 0; 81 }