題意：
? ? ?給你一個字典，最多4000個單詞，每個單詞長度最多是100，然后給你一個串，問你這個子串可以被那些單詞組合的組合數，比如字典里有4個單詞a b ab cd，然后給你一個串abcd則abcd = a+b+cd,ab+cd一共兩種組合。輸出組合數對20071027取余（白書上寫錯了寫的是20071207）


思路：
? ? ? ?我們可以找到一個遞推公式，d[i] = sum(i + len[x]),解釋一下這個，d[i]表示的是以i個位置為開頭的字符串的組合個數，就是[i,i+1,i+2..len-1],而x則是以i開頭的那個串的前綴，這樣就不難理解了吧，整體意思就是如果defg = 5,那么只要存在bc，就可以得到以a開頭的abcdefg可以加上5了，然后就是優化時間，因為直接暴力寫的話30000*4000*判斷前綴匹配，時間復雜度接受不了，既然是前綴，我們可以想到字典樹，我們可以把所有的4000個單詞都放到字典里，然后在匹配的時候如果碰到單詞末尾節點，直接就是找到滿足條件，更新左右值，就行了，具體看代碼，很容易理解。
PS不要把30000的那個字符串拆開放到字典樹里，一開始我就是這么想的，結果還沒敲完意識到這樣內存會很大，很可能會爆內存，還有就是別忽視strlen這個函數的時間復雜度，TLE了一次。
? ? ??




#include<stdio.h>
#include<string.h>
#include<stdlib.h>


#define N 300000 + 10
#define MOD 20071027


typedef struct Tree
{
? ? Tree *next[26];
? ? int mk;
}Tree;


Tree root;
char Str[N];
long long dp[N];


void BuidTree(char *str)
{
? ? int len = strlen(str);
? ? Tree *p = &root ,*q;
? ? for(int i = 0 ;i < len ;i ++)
? ? {
? ? ? ? int id = str[i] - 'a';
? ? ? ? if(p -> next[id] == NULL)
? ? ? ? {
? ? ? ? ? ? q = (Tree *)malloc(sizeof(root));
? ? ? ? ? ? q -> mk = 0;
? ? ? ? ? ? for(int j = 0 ;j < 26 ;j ++)
? ? ? ? ? ? q -> next[j] = NULL;
? ? ? ? ? ? p -> next[id] = q;
? ? ? ? ? ? p = p -> next[id];
? ? ? ? }
? ? ? ? else
? ? ? ? p = p -> next[id];
? ? }
? ? p -> mk = 1;
}


void Query(char *str ,int ii ,int len)
{
? ? dp[ii] = 0;
? ? Tree *p = &root;
? ? for(int i = ii ;i < len ;i ++)
? ? {
? ? ? ? int id = str[i] - 'a';
? ? ? ? p = p -> next[id];
? ? ? ? if(p == NULL) break;
? ? ? ? if(p -> mk) dp[ii] = (dp[ii] + dp[i+1]) % MOD;
? ? }
? ? return ;
}


int main ()
{
? ? int cas = 1 ,i ,n;
? ? char tmp[105];
? ? while(~scanf("%s" ,Str))
? ? {
? ? ? ? scanf("%d" ,&n);
? ? ? ? for(i = 0 ;i < 26 ;i ++)
? ? ? ? root.next[i] = NULL;
? ? ? ? for(i = 1 ;i <= n ;i ++)
? ? ? ? {
? ? ? ? ? ? scanf("%s" ,tmp);
? ? ? ? ? ? BuidTree(tmp);
? ? ? ? }
? ? ? ? int len = strlen(Str);
? ? ? ? dp[len] = 1;
? ? ? ? for(i = len - 1 ;i >= 0 ;i --)
? ? ? ? {
? ? ? ? ? ? Query(Str ,i ,len);//把len直接傳下去，別在里面從求，會超時。
? ? ? ? }
? ? ? ? printf("Case %d: %lld\n" ,cas ++ ,dp[0]);
? ? }
}

總結

以上是生活随笔為你收集整理的LA3942字典树+递推的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。