题目
点这里看题目。
分析
补习知识:
既然可以求出原串中不同的子串的个数,那么我们同样可以求出含重复子串的个数,同样是\(dp\):
\(g(u)\):从\(u\)节点出发含重复的子串的数量。
转移:
\[g(u)=|end-pos(u)|+\sum_{(u,v)\in DAWG} g(v) \]
因为可以重复,所以对于一个子串,它的出现次数就是它的结尾的\(end-pos\)的大小。
正解部分,对于\(t=0\)的情况,就是一个模板题。对于\(t=1\)的情况,套用\(t=0\)的方法,这个时候我们改用\(g\)来确定该走哪一步。
代码
#include <cstdio>
#include <cstring>
const int MAXN = 5e5 + 5;
template<typename _T>
void read( _T &x )
{
x = 0; char s = getchar();int f = 1;
while( s < '0' || '9' < s ) { f = 1; if( s == '-' ) f = -1; s = getchar(); }
while( '0' <= s && s <= '9' ) { x = ( x << 3 ) + ( x << 1 ) + s - '0', s = getchar(); }
x *= f;
}
template<typename _T>
void write( _T x )
{
if( x < 0 ) { putchar( '-' ), x = -x; }
if( 9 < x ) { write( x / 10 ); }
putchar( x % 10 + '0' );
}
struct edge
{
int to, nxt;
}Graph[MAXN << 1];
int f[MAXN << 1], g[MAXN << 1];
int cnt[MAXN];
int ep[MAXN << 1], seq[MAXN << 1], head[MAXN << 1];
int ch[MAXN << 1][26], fa[MAXN << 1], mx[MAXN << 1];
char A[MAXN];
int N, T, K, rt, lst, tot, ecnt;
void addEdge( const int from, const int to )
{
ecnt ++;
Graph[ecnt].to = to, Graph[ecnt].nxt = head[from];
head[from] = ecnt;
}
void copy( const int a, const int b ) { fa[a] = fa[b], mx[a] = mx[b], memcpy( ch[a], ch[b], sizeof ch[b] ); }
void expand( const char c )
{
int x = c - 'a', p = lst, cur = ++ tot;
mx[cur] = mx[p] + 1, lst = cur, ep[cur] = 1;
while( p && ! ch[p][x] ) ch[p][x] = cur, p = fa[p];
if( ! p ) { fa[cur] = rt; return ; }
int q = ch[p][x];
if( mx[q] == mx[p] + 1 ) { fa[cur] = q; return ; }
int nq = ++ tot; copy( nq, q );
mx[nq] = mx[p] + 1, fa[cur] = fa[q] = nq;
while( p && ch[p][x] == q ) ch[p][x] = nq, p = fa[p];
}
void topo()
{
for( int i = 1 ; i <= tot ; i ++ ) cnt[mx[i]] ++;
for( int i = 1 ; i <= N ; i ++ ) cnt[i] += cnt[i - 1];
for( int i = tot ; i ; i -- ) seq[cnt[mx[i]] --] = i;
}
void DFS( const int u )
{
for( int i = head[u], v ; i ; i = Graph[i].nxt )
DFS( v = Graph[i].to ), ep[u] += ep[v];
}
int main()
{
scanf( "%s", A + 1 ); N = strlen( A + 1 );
read( T ), read( K );
rt = lst = ++ tot;
for( int i = 1 ; i <= N ; i ++ )
expand( A[i] );
for( int i = 2 ; i <= tot ; i ++ ) addEdge( fa[i], i );
DFS( 1 ), topo();
for( int i = tot, u ; i ; i -- )
{
if( ( u = seq[i] ) > 1 ) { f[u] = 1, g[u] = ep[u]; }
for( int j = 0 ; j < 26 ; j ++ )
if( ch[u][j] ) f[u] += f[ch[u][j]], g[u] += g[ch[u][j]];
}
if( K > f[1] ) { write( -1 ); return 0; }
if( T )
{
int p = rt, v;
while( true )
{
for( int i = 0 ; i < 26 ; i ++ )
{
v = ch[p][i];
if( K <= ep[v] ) { putchar( 'a' + i ), putchar( '\n' ); return 0; }
else if( K <= g[v] ) { putchar( 'a' + i ), K -= ep[v], p = ch[p][i]; break; }
K -= g[v];
}
}
putchar( '\n' );
}
else
{
int p = rt, v;
while( K )
{
for( int i = 0 ; i < 26 ; i ++ )
{
v = ch[p][i];
if( f[v] >= K ) { p = ch[p][i], putchar( 'a' + i ), K --; break; }
K -= f[v];
}
}
putchar( '\n' );
}
return 0;
}