甲苯先生和大中锋的字符串

题目：[TJOI2019]甲苯先生和大中锋的字符串

大中锋有一个长度为 n 的字符串，他只知道其中的一个子串是祖上传下来的宝藏的密码。但是由于字符串很长，大中锋很难将这些子串一一尝试。

这天大中锋找到甲苯先生算命，但是甲苯先生说：“天机不可泄漏”。

在大中锋的苦苦哀求下，甲苯先生告诉大中锋：“密码是在字符串中恰好出现了 kk 次的子串”。

但是大中锋不知道该怎么做，在大中锋再三的恳求下，甲苯先生看其真诚，又告诉他：“在恰好出现了 k 次的子串中，你去按照字串的长度分类，密码就在数量最多的那一类里”。

大中锋为了尝试这个密码，想让你帮忙找出子串长度出现次数最多的长度数（如果有多个输出最长长度）。

题解（后缀数组）：

后缀数组好题，题解说是大水题，但我看不出来。

题还是做得太少，对后缀数组的理解也太浅。

我们用一个长度为k的滑块去滑字符串。

字符串的先后顺序是按后缀排序来的。

我们维护了区间的最小height值，记为x，

这是什么？

如果x为0，说明这样的前缀失败了，出现次数不到k

如果x不为0，说明此时长度为x的前缀至少有k个

但我们要求恰好为k的个数

那怎么办呢？

有了，我们判一下,h[i-k+1]和h[i+1]

如果这两个值中有值大于等于x，这说明此时长度为x的前缀超过了k个

否则这样长度为x的前缀恰好等于k个。

考虑前缀中能分出多少的前缀恰好等于k，最小的就是max(h[i-k+1],h[i+1])+1,最大的是x

计算答案就差分一下即可，维护最大值 .

代码：

#include
using namespace std;
#define next Next
const int N=4e5+5;
int n,m,k,q[N],cf[N],sa[N],height[N],x[N],y[N],c[N],rk[N];
char a[N];
/*char buf[1<<21],*p1=buf,*p2=buf;
inline int gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}*/
#define gc getchar
inline int read()
{
    int ret=0,f=0;char c=gc();
    while(!isdigit(c)){if(c=='-')f=1;c=gc();}
    while(isdigit(c)){ret=ret*10+c-48;c=gc();}
    if(f)return -ret;return ret;
}
void SA(int n,int m)
{
    int p;
    for(int i=0;i<=n;i++)
    {
        sa[i]=rk[i]=x[i]=y[i]=0;
    }
    for(int i=1;i<=m;i++)c[i]=0;
    for(int i=1;i<=n;i++)c[x[i]=a[i]]++;
    for(int i=1;i<=m;i++)c[i]+=c[i-1];
    for(int i=n;i;i--)sa[c[x[i]]--]=i;
    for(int i=1;i;i=i*2)
    {
        p=0;
        for(int j=n-i+1;j<=n;j++)y[++p]=j;
        for(int j=1;j<=n;j++)
            if(sa[j]>i)y[++p]=sa[j]-i;
        for(int j=1;j<=m;j++)c[j]=0;
        for(int j=1;j<=n;j++)c[x[y[j]]]++;
        for(int j=1;j<=m;j++)c[j]+=c[j-1];
        for(int j=n;j;j--)sa[c[x[y[j]]]--]=y[j];
        swap(x,y);
        x[sa[1]]=1;
        p=2;
        for(int j=2;j<=n;j++)
        {
            if(y[sa[j]]==y[sa[j-1]]&&y[sa[j]+i]==y[sa[j-1]+i])x[sa[j]]=p-1;
            else x[sa[j]]=p++;
        }
        if(p>n)return;
        m=p;
    }
}
void Height()
{
    int k=0;
    for(int i=1;i<=n;i++)rk[sa[i]]=i;
    for(int i=1;i<=n;i++)
    {
        if(rk[i]==1)continue;
        if(k)k--;
        int j=sa[rk[i]-1];
        while(i+k<=n&&j+k<=n&&a[i+k]==a[j+k])k++;
        height[rk[i]]=k;
    }
}
signed main()
{
    int T=read();
    while(T--)
    {
        memset(cf,0,sizeof(cf));
        scanf("%s",a+1);
        n=strlen(a+1);
        k=read();
        height[n+1]=0;
        SA(n,122);
        Height();
        int l=1,r=0;
        for(int i=1;i<=k;i++)
        {
            while(l=height[i])r--;
            q[++r]=i;
        }
        for(int i=k;i<=n;i++)
        {
            if(i-q[l]+1>=k)l++;
            while(l=height[i])r--;
            q[++r]=i;
            int R;
            if(k==1)R=n-sa[i+k-1]+1;
            else R=height[q[l]];
            int L=max(height[i-k+1],height[i+1]);
            if(L<R)
            {
                cf[L+1]++;
                cf[R+1]--;
            }
        }
        int sum=cf[0],ma=1,ans=-1;
        for(int i=1;i<=n;i++)
        {
            sum+=cf[i];
            if(sum>=ma)
            {
                ma=sum;
                ans=i;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}
/*
后缀数组好题，题解说是大水题，但我看不出来。
题还是做得太少，对后缀数组的理解也太浅。
我们用一个长度为k的滑块去滑字符串。
字符串的先后顺序是按后缀排序来的。
我们维护了区间的最小height值，记为x，
这是什么？
如果x为0，说明这样的前缀失败了，出现次数不到k
如果x不为0，说明此时长度为x的前缀至少有k个
但我们要求恰好为k的个数
那怎么办呢？
有了，我们判一下,h[i-k+1]和h[i+1]
如果这两个值中有值大于等于x，这说明此时长度为x的前缀超过了k个
否则这样长度为x的前缀恰好等于k个。
考虑前缀中能分出多少的前缀恰好等于k，最小的就是max(h[i-k+1],h[i+1])+1,最大的是x
计算答案就差分一下即可，维护最大值 .
*/