弦论

一道板子题,让我感觉板子题都还不会。。。然后把递推写成dfs时没有给string加上&,导致内存爆了,2333,果然还是传引用好

题意:求字典序第K小子串以及本质不同的第K小子串

思路:

  1. 正常的建好后缀自动机
  2. 由于处理一个节点有多少endpos以及经过一个节点有多少子串都需要将所以节点按len从大到小排序,因此就不采用topo排序了
  3. 利用一次计数排序,即可完成长度排序,得到长度第i短的子串为a[i]
  4. 然后就是进行两个处理:endpos(cnt数组)大小以及size大小
  5. 最后是贪心的构建字典序第K小子串,但要记住当前节点字典序要比在后面增添字符后的字典序的小,所以要先考虑当前节点

题目描述

为了提高智商,ZJY开始学习弦论。这一天,她在《 String theory》中看到了这样一道问题:对于一个给定的长度为n的字符串,求出它的第k小子串是什么。你能帮帮她吗?

输入格式

第一行是一个仅由小写英文字母构成的字符串s

第二行为两个整数t和k,t为0则表示不同位置的相同子串算作一个,t为1则表示不同位置的相同子串算作多个。k的意义见题目描述。

输出格式

输出数据仅有一行,该行有一个字符串,为第k小的子串。若子串数目不足k个,则输出-1。

输入输出样例(有点难看,删掉了)

//#pragma comment(linker, "/STACK:102400000,102400000")
#include "bits/stdc++.h"
#define pb push_back
#define ls l,m,now<<1
#define rs m+1,r,now<<1|1
#define hhh printf("hhh\n")
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline int read() {int x=0;char c=getchar();while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x;}

const int maxn = 1e6+10;
const int mod = 1e9+7;
const double eps = 1e-9;

char s[maxn];
int ch[maxn][26], fa[maxn], cnt[maxn], son[maxn], len[maxn];
int last=1, sz=1, n, a[maxn], c[maxn];
ll size[maxn];

void add(int c) {
    int p=last, np=last=++sz;
    len[np]=len[p]+1, cnt[np]=1;
    for(; p&&!ch[p][c]; p=fa[p]) ch[p][c]=np;
    if(!p) fa[np]=1;
    else {
        int q=ch[p][c];
        if(len[q]==len[p]+1) fa[np]=q;
        else {
            int nq=++sz;
            fa[nq]=fa[q], len[nq]=len[p]+1;
            memcpy(ch[nq],ch[q],104);
            fa[q]=fa[np]=nq;
            for(; p&&ch[p][c]==q; p=fa[p]) ch[p][c]=nq;
        }
    }
}

void solve(int now, int k, string &l) {
    if(k>size[now]) {
        cout<<-1<<endl;
        return;
    }
    if(k<=cnt[now]) {
        cout<<l<<endl;
        return;
    }
    k-=cnt[now];
    for(int i=0; i<26; ++i) {
        int v=ch[now][i];
        if(v&&k<=size[v]) {
            solve(v,k,l+=char(i+'a'));
            return;
        }
        k-=size[v];
    }
}

int main() {
    //ios::sync_with_stdio(false);
    scanf("%s", s); n=strlen(s);
    int t=read(), k=read();
    for(int i=0; i<n; ++i) add(s[i]-'a');
    
    for(int i=1; i<=sz; ++i) c[len[i]]++;
    for(int i=1; i<=sz; ++i) c[i]+=c[i-1];
    for(int i=1; i<=sz; ++i) a[c[len[i]]--]=i;

    for(int i=sz; i; --i)
        if(t) cnt[fa[a[i]]]+=cnt[a[i]];
        else cnt[a[i]]=1;
    cnt[1]=0; //cnt[1]本来等于字符串长度n的
    for(int i=sz; i; --i) {
        size[a[i]]=cnt[a[i]];
        for(int j=0; j<26; ++j)
            if(ch[a[i]][j]) size[a[i]]+=size[ch[a[i]][j]];
    }
    string l;
    solve(1,k,l);
}