首页 > 代码库 > 【bzoj3998】[TJOI2015]弦论 后缀自动机+dp
【bzoj3998】[TJOI2015]弦论 后缀自动机+dp
题目描述
对于一个给定长度为N的字符串，求它的第K小子串是什么。
输入
第一行是一个仅由小写英文字母构成的字符串S
第二行为两个整数T和K，T为0则表示不同位置的相同子串算作一个。T=1则表示不同位置的相同子串算作多个。K的意义如题所述。
输出
输出仅一行，为一个数字串，为第K小的子串。如果子串数目不足K个，则输出-1
样例输入
aabc
0 3
样例输出
aab
题解
后缀自动机+dp
先对原串建立后缀自动机，然后在其上面跑dp统计每个节点开始的串的个数。
设f[i]表示与位置i有相同前缀的串的个数。
那么当T=0时，显然f[i]=∑f[son[i]]+1。
当T=1时，f[i]=∑f[son[i]]+|right[i]|，需要统计right集合的大小，也即统计parent树中子树内有多少个叶子结点，这个递推一下即可。
在这里边需要保证son[i]在i之前更新，所以需要得到拓扑序。
然后大爷说会卡常？这里orz hzwer，对dis排序即可得到拓扑序，而且可以使用基数排序，详见代码。
最后求一下和，dfs一遍就好了，类似于二（十六）分。
#include <cstdio>#include <cstring>#include <algorithm>#define N 1000010using namespace std;int n , opt , next[N][26] , fa[N] , dis[N] , last = 1 , tot = 1 , v[N] , q[N] , cnt[N] , sum[N];char str[N];void ins(int c){ int p = last , np = last = ++tot; dis[np] = dis[p] + 1 , cnt[np] = 1; while(p && !next[p][c]) next[p][c] = np , p = fa[p]; if(!p) fa[np] = 1; else { int q = next[p][c]; if(dis[q] == dis[p] + 1) fa[np] = q; else { int nq = ++tot; memcpy(next[nq] , next[q] , sizeof(next[q])) , dis[nq] = dis[p] + 1 , fa[nq] = fa[q] , fa[np] = fa[q] = nq; while(p && next[p][c] == q) next[p][c] = nq , p = fa[p]; } }}void init(){ int i , j , t; for(i = 1 ; i <= tot ; i ++ ) v[dis[i]] ++ ; for(i = 1 ; i <= n ; i ++ ) v[i] += v[i - 1]; for(i = tot ; i ; i -- ) q[v[dis[i]] -- ] = i; for(i = tot ; i ; i -- ) { t = q[i]; if(opt) cnt[fa[t]] += cnt[t]; else cnt[t] = 1; } cnt[1] = 0; for(i = tot ; i ; i -- ) { t = q[i] , sum[t] = cnt[t]; for(j = 0 ; j < 26 ; j ++ ) sum[t] += sum[next[t][j]]; }}void query(int p , int k){ if(k <= cnt[p]) return; k -= cnt[p]; int i; for(i = 0 ; i < 26 ; i ++ ) { if(next[p][i]) { if(k <= sum[next[p][i]]) { putchar(i + ‘a‘) , query(next[p][i] , k); return; } k -= sum[next[p][i]]; } }}int main(){ int k , i; scanf("%s%d%d" , str + 1 , &opt , &k) , n = strlen(str + 1); for(i = 1 ; i <= n ; i ++ ) ins(str[i] - ‘a‘); init(); if(k > sum[1]) printf("-1"); else query(1 , k); return 0;}
【bzoj3998】[TJOI2015]弦论 后缀自动机+dp
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。