[TJOI2015]弦论

· · 题解

题目

        点这里看题目。

分析

        补习知识：
        既然可以求出原串中不同的子串的个数，那么我们同样可以求出含重复子串的个数，同样是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;
}