【题解】P2922 [USACO08DEC]秘密消息Secret Message

• 　\(\text{Tags}\)

  • 字典树，统计

• 　题意：

  • 给出两组\(\text{0/1}\)串\(\text{A,B}\)，求解\(\text{A}\)中某串是\(\text{B}\)中某串的前缀，和\(\text{B}\)中某串是\(\text{A}\)中某串的前缀的数量之和。

• 分析：

  • 对于\(\text{A}\)建立字典树。另外附加两个数组：
  • \(\text{int Son[i]}\)表示节点 \(\text{i}\) 点\(\text{Son[i]}\)儿子。
  • \(\text{int End[i]}\)表示有\(\text{End[i]}\)个字符串终结于\(\text{i}\)。
  • 对于每个询问，沿着字典树向下走，累加沿途的\(\text{End[i]}\) 。
  • 如果不能匹配，返回累加值。
  • 如果整个询问都匹配成功，还要加上最后一个节点的儿子数量。

• 参考代码：

  • #include <stdio.h>
    #include <string.h>
    #define re register
    #define GC getchar()
    #define Clean(X,K) memset(X,K,sizeof(X))
    int Qread () {
        int X = 0 ;
        char C = GC ;
        while (C > '9' || C < '0') C = GC ;
        while (C >='0' && C <='9') {
            X = X  * 10 + C - '0' ;
            C = GC ;
        }
        return X ;
    }
    const int Maxn = 500005 , Base = 2;
    int T[Maxn][Base] , Tot = 0 , M , N , End[Maxn] , Son[Maxn] , A[Maxn];
    void Add (int Now) {
        int P = 0 ;
        for (re int i =  0 ; i < Now ; ++ i) {
            if (!T[P][A[i]]) T[P][A[i]] = ++ Tot;
            ++ Son[P] ;
            P = T[P][A[i]] ;
        }
        ++ End[P] ;
    }
    int Ask (int Now) {
        int P = 0 , Ans = 0;
        for (re int i = 0 ; i < Now ; ++ i) {
            if (!T[P][A[i]]) return Ans ;
            P = T[P][A[i]] ;
            Ans += End[P] ;
        }
        return Ans + Son[P] ;
    }
    int main () {
        M = Qread () , N = Qread () ;
        Clean(T , 0) , Clean(End , 0) , Clean (Son , 0) ;
        for (re int i = 1 ; i <= M; ++ i) {
            int Now = Qread () ;
            for (re int j = 0 ; j < Now ; ++ j) A[j] = Qread () ;
            Add (Now) ;
        }
        for (re int i = 1 ; i <= N; ++ i) {
            int Now = Qread () ;
            for (re int j = 0 ; j < Now ; ++ j) A[j] = Qread () ;
            printf ("%d\n" , Ask (Now)) ;
        }
        fclose (stdin) , fclose (stdout) ;
        return 0 ;
    }

　Thanks!

【题解】P2922 [USACO08DEC]秘密消息Secret Message

原文：https://www.cnblogs.com/bj2002/p/10595092.html