uva 1401 Remember the Word ( Trie + DP )

uva 1401 Remember the Word ( Trie + DP )

題意：給出n（n<=4000）個單詞和一個字符串（len<=300000），求把這個字符串分解成若干個單詞的拼接，有多少種方法

思路：Trie，先把單詞建成Trie，然後進行dp，dp[i]表示以字符串中第i個字母為開頭的情況，然後每個狀態只要在Trie樹上找到相應的字母開頭的單詞，然後dp[i] = sum{dp[i + len（x）]}進行狀態轉移即可 這個x是n個單詞中的一個，可以用Trie查詢

code：

#include
#include
#include
using namespace std;

const int maxn = 300005;
const int MOD = 20071027;

int ch[maxn][26];
int val[maxn];
int sz;
int idx(char c){return c-'a';}
void insert(char* s){
    int u = 0;
    int len = strlen(s);
    for(int i = 0; i < len; i++){
        int c = idx(s[i]);
        if(!ch[u][c]){
            memset(ch[sz], 0, sizeof(ch[sz]));
            val[sz] = 0;
            ch[u][c] = sz++;
        }
        u = ch[u][c];
    }
    val[u] = 1;
}

void init(){
    sz = 1;
    memset(ch[0],0,sizeof(ch[0]));
    int m;
    scanf("%d",&m);
    char str[105];
    while(m--){
        scanf("%s",str);
        insert(str);
    }
}
int d[maxn];
void find(int id, char* s){
    d[id] = 0;
    int u = 0;
//    int len = strlen(s);
    for(int i = id; s[i]; i++){
        int c = idx(s[i]);
        if(!ch[u][c]) return;
        u = ch[u][c];
        if(val[u]) d[id] = (d[id]+d[i+1])%MOD;
    }
}
void solve(char* s){
    int len = strlen(s);
    d[len] = 1;
    for(int i = len-1; i >= 0; i--){
        find(i, s);
    }
    printf("%d\n",d[0]);
}
int main(){
    int cas = 0;
    char s[maxn];
    while(scanf("%s",s) != EOF){
        init();
        printf("Case %d: ",++cas);
        solve(s);
    }
    return 0;
}

find 函數中千萬不能strlen（）；不然超時T_T。。因為每次調用都會求一次長度，時間復雜度是0（N*N）；