P2922 秘密消息Secret Message

chihik · 2019-07-15 21:34:56 · 题解

这道题还是Trie树的板题，先将n个信息插入字典树中，对于查询的密码，在字典树中查询即可。

插入很好办，我们现在来讨论查询操作。我们记s_1为任意一个信息，s_2是待匹配的密码。tot[u]表示有多少个字符串经过点u，fin[u]表示有多少个字符串以点u结尾。

那么会出现三种情况：

1.s_1是s_2的前缀，累加路径上所有的fin[u]即可。

2.s_1=s_2。其实就是情况1，s_1结束时的点一定与s_2结束时的点相同，也就包含在fin中。

3.s_2是s_1的前缀，如果单词最后一个字符所在节点为v，我们很容易看出tot[v]就代表该单词是多少字符串的前缀。那么我们只需要加上tot[v]就好了。

但是，tot[v]会包含以v节点结尾的单词数，所以结果须减去fin[v]。

那么，一道难蓝题就被我们解决了，附上代码：

#include <cstdio>
#include <cstring>

const int MAXN = 500000;
int n,m,len;
int Trie[ MAXN + 5 ][ 2 ] , cnt;
int tot[ MAXN + 5 ] , fin[ MAXN + 5 ];

void Insert( char *str , int len ) {
    int u = 0;
    for( int i = 0 ; i < len ; i ++ ) {
        int num = str[ i ] - '0';
        if( !Trie[ u ][ num ] ) 
            Trie[ u ][ num ] = ++ cnt;
        u = Trie[ u ][ num ];
        tot[ u ] ++;
    }
    fin[ u ] ++;
}
int Find( char *str , int len ) {
    int u = 0 , Ans = 0;
    for( int i = 0 ; i < len ; i ++ ) {
        int num = str[ i ] -'0';
        if( !Trie[ u ][ num ] )
            return Ans;
        u = Trie[ u ][ num ];
        Ans += fin[ u ];
    }
    return Ans - fin[ u ] + tot[ u ];
}

int s1;
char s[ 10005 ];
int main( ) {
    scanf("%d %d",&m,&n);
    for( int i = 1 ; i <= m ; i ++ ) {
        scanf("%d",&len);
        for( int j = 0 ; j < len ; j ++ ) {
            scanf("%d",&s1);
            s[ j ] = s1 + '0';
        }
        Insert( s , len );
    }
    for( int i = 1 ; i <= n ; i ++ ) {
        scanf("%d",&len);
        for( int j = 0 ; j < len ; j ++ ) {
            scanf("%d",&s1);
            s[ j ] = s1 + '0';
        }
        printf("%d\n",Find( s , len ));
    }
    return 0;
}