Tire树的学习

Tire树是一种基于空间换时间思想的，应用于字符串处理的数据结构。

题目地址

分析：设DP数组Can[MaxL]，Can[i]=1表示第i位可以理解。

　　当Can[i]==1，对第i+1位进行匹配，若能匹配完整的单词，那么也是可以理解的。

　　另外注意使用getline会读进来一些奇怪的东西。

#include <stdio.h>
#include <string.h>
#define re register
#define GC getchar()
#include <string>
#define Clean(X,K) memset(X,K,sizeof(X))
#include <iostream>
#define Max(A,B) (A>B?A:B)
using namespace std ;
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 = 22 , MaxL = 12 , Base = 26 , INF = 20021020 << 2;
int N , M, T[Maxn * MaxL][Base] , Tot = 0 , End[Maxn * MaxL] , Can[1000000] , Len , Ans = 0;
string S ;
void Add () {
    int P = 0 , L = S.length() ;
    for (re int i = 0 ; i < L; ++ i) {
        if (!T[P][S[i]-'a']) T[P][S[i]-'a'] = ++ Tot ;
        P = T[P][S[i] - 'a'] ;
    }
    End[P] = INF ;
}
void Ask (int From ) {
    int P = 0 ;
    for (re int i = From ; i < Len ; ++ i) {
        if (!T[P][S[i] - 'a']) return ;
        P = T[P][S[i] - 'a'] ;
        if (End[P]) {
            Can[i] = INF ;
            Ans = Max (Ans , i + 1); 
        }
    }
}
int main () {
//    freopen ("P2292.in" , "r" , stdin) ;
    N = Qread () , M = Qread () ;
    Clean (T , 0) , Clean (End , 0);
    for (re int i = 0 ; i < N; ++ i) {
        cin >> S ;
        Add () ;
    }
    for (re int i = 0 ; i < M; ++ i) {
        cin >> S ;
        Clean (Can , 0) , Ans=  0, Len = S.length() ;
        Ask (0) ;
        for (re int j = 0 ; j < Len ;++ j) if (Can[j]) Ask (j + 1) ;
        printf ("%d
" , Ans) ;
    }
    fclose (stdin) , fclose (stdout) ;
    return 0 ;
}