P3975 [TJOI2015]弦论

题意：

给出两个整数$t$ , $k$，$t$为0则表示不同位置的相同子串算作一个,$t$为$1$则表示不同位置的相同子串算作多个。让你求出字符串的第$k$小子串是什么。

题解：

我们首先只考虑如何输出第k小的子串，很显然，有一个性质，首位字符越小，子串排名越靠前，我们可以考虑一个字符一个字符的枚举，若第k小的子串是以当前字符开头的，那么就往下走，否则枚举下一个字符，再减去这个字符开头的子串个数。也就是说，我们现在的问题变成了统计以后缀自动机上某一个节点开头的子串的个数，这个问题就变得简单了。

对于$t=0$的情况，我们知道$endpos$集合表示的是结束位置的子串集合，那么$endpos$集合的大小就表示当前结束位置相同的子串的个数等价于当前已经匹配到的字符串的出现次数。因为相同子串只算一次，所以只需要把所有的$endpos$集合大小赋值为1即可。

对于$t=1$的情况，我们可以建出$parent$树，然后基数排序，倒序$for$循环跑一遍求出所有$endpos$集合大小。考虑用另外一个数组sum，表示的是$endpos$集合在后缀自动机意义下的前缀和，$sum[u]$表示以一个在后缀自动机上，编号为u的节点作为前缀的子串个数。

$AC$代码：

#include<bits/stdc++.h> using namespace std; const int MAXN = 1e6+50; inline int read(){ int x=0,f=1; char ch=getchar(); while(!isdigit(ch)){ if(ch=='-') ch=-1; ch = getchar(); } while(isdigit(ch)) x=x*10+ch-48,ch=getchar(); return x*f; } char s[MAXN]; struct Suffix{ int nxt[MAXN][26],fa[MAXN],len[MAXN],sz[MAXN],sum[MAXN]; int c[MAXN],a[MAXN]; int last=1,tot=1; inline void Insert(int x){ int p = last,np = ++tot; last = np,len[np] = len[p] + 1; for(;p && !nxt[p][x];p=fa[p]) nxt[p][x] = np; if(!p) fa[np] = 1; else { int q = nxt[p][x]; if(len[p]+1 == len[q]) fa[np] = q; else { int nq = ++tot; len[nq] = len[p] + 1; memcpy(nxt[nq],nxt[q],sizeof(nxt[q])); fa[nq] = fa[q]; fa[q] = fa[np] = nq; for(;nxt[p][x]==q;p=fa[p]) nxt[p][x] = nq; } } sz[np] = 1; } inline void Solve(int f,int k){ for(int i=1;i<=tot;i++) c[len[i]]++; for(int i=1;i<=tot;i++) c[i]+=c[i-1]; for(int i=1;i<=tot;i++) a[c[len[i]]--]=i; for(int i=tot;i;i--) if(!f) sz[a[i]] = 1; else sz[fa[a[i]]] += sz[a[i]]; sz[1]=0; for(int i=tot;i;i--){ sum[a[i]] = sz[a[i]]; for(int j=0;j<26;j++) sum[a[i]] += sum[nxt[a[i]][j]]; } if(k > sum[1]) { puts("-1");return; } int u = 1; while(k>0){ int p = 0; while(k>sum[nxt[u][p]]) k -= sum[nxt[u][p]],p++; u = nxt[u][p]; putchar(p+'a'); k -= sz[u]; } return; } }SAM; int main(){ scanf("%s",s+1); int f = read(),n = read(); for(int i=1;s[i];i++) SAM.Insert(s[i]-'a'); SAM.Solve(f,n); return 0; }