题目地址:https://cn.vjudge.net/problem/SPOJ-SUBLEX
解题思路:
这道题用后缀数组也很好做,参见例题HDU5008,此处用SAM做。
建好SAM,根据得到的拓扑序,可以推得从每个状态出发的子串数目。
void getsum()//从某个状态点出发能有多少个子串
{
//倒推,i是拓扑序的序号
for(int i = num; i >= 1; i--)
{
sum[y[i]] = 1;//默认值为1,因为从自己不出发就能形成一个子串
for(int j = 0; j <= 25; j++)
sum[y[i]] += sum[trans[y[i]][j]];
}
}
现在相当于得到一个这样的东西:
现在只需利用getsum函数得到的信息在这个上面寻找字典序第k小的子串了
ac代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 9e4+100;
int maxlen[maxn<<1], trans[maxn<<1][30], link[maxn<<1];
int x[maxn<<1], y[maxn<<1], cnt[maxn<<1];
int num, last;//num表示状态数
char s[maxn];
int sum[maxn<<1];//与状态数有关,开两倍
void init()
{
num = last = 1;//起始状态的编号为1
maxlen[last] = link[last] = 0;//起始位置为空字符,长度为0
}
void insert(int id)
{
int z = ++num, p;
maxlen[z] = maxlen[last]+1;
for(p = last; p && !trans[p][id]; p = link[p]) trans[p][id] = z;
if(!p) link[z] = 1;//路径上不存在跳转
else//连接路径上已存在跳转
{
int x = trans[p][id];//第一个存在跳转的状态跳转去的状态
if(maxlen[x] == maxlen[p]+1) link[z] = x;//一个
else//多个
{
int y = ++num;
maxlen[y] = maxlen[p]+1;
memcpy(trans[y], trans[x], sizeof(trans[x]));
link[y] = link[x];
for(; p && trans[p][id] == x; p = link[p]) trans[p][id] = y;
link[x] = link[z] = y;
}
}
last = z;
cnt[z] = 1;
}
void count()
{
memset(x, 0, sizeof x);
for(int i = 1; i <= num; i++) x[maxlen[i]]++;
for(int i = 1; i <= num; i++) x[i] += x[i-1];
for(int i = 1; i <= num; i++) y[x[maxlen[i]]--] = i;
for(int i = num; i >= 1; i--)
cnt[link[y[i]]] += cnt[y[i]];//得到每个状态的字符串集出现的次数
}
void getsum()//从某个状态点出发能有多少个子串
{
//倒推,i是拓扑序的序号
for(int i = num; i >= 1; i--)
{
sum[y[i]] = 1;//默认值为1,因为从自己不出发就能形成一个子串
for(int j = 0; j <= 25; j++)
sum[y[i]] += sum[trans[y[i]][j]];
}
}
void get_Ksub(int k)
{
int cur = 1, nxt;
string ans = "";
while(k)
{
for(int i = 0; i <= 25; i++)
{
if(trans[cur][i] && k)
{
nxt = trans[cur][i];
if(k > sum[nxt]) k -= sum[nxt];
else
{
k--;//字典序增大1
cur = nxt;
ans += char(i+'a');
break;
}
}
}
}
cout << ans << endl;
}
int main()
{
scanf("%s", s);
int len = strlen(s), q, k;
init();
for(int i = 0; i < len; i++) insert(s[i]-'a');
count();
getsum();
scanf("%d", &q);
while(q--)
{
scanf("%d", &k);
get_Ksub(k);
}
return 0;
}