Remember The Word-Trie

题目： UVaLive 3942

#include<cstdio>
#include<cstring>

using namespace std;

const int MAX = 4010 * 100;         //题目中说过每个样例S<4000 单个长度<100
const int MOD = 20071027;
int sz = 1;                         //用来记录每个字母的顺序
char str;
int ch[MAX][26];
int flag[MAX];                      //用来标识每个单词是否已经结束
int ans[300010];

void clearw(){
    sz = 1;    
    memset(ch[0],0,sizeof(ch[0]));
    memset(flag,0,sizeof(flag));
}
//创建一个新的字母节点
int creatw(int u){
    memset(ch[sz],0,sizeof(ch[sz]));
    flag[sz] = u;
    return  sz++;
}                       
/*插入函数：用来插入新的单词，如果在这一层已经存在这个字母了，继续往下摸，否则就
 *创建一个新的节点,在单词的最后设立一个结束的哨兵。这样建成一棵字典树。
 */
int insertw(char *s){
    int u = 0;
    int len = strlen(s);
    for(int i = 0;i < len;i++){
        int v = s[i] - 'a';
        if(!ch[u][v])
            ch[u][v] = creatw(0);
        u = ch[u][v];
    }
    flag[u] = 1;
}
/*查找函数：根据给定的深度和字符串开始搜索。依然是用s[i]-'a'来判断那个对应的位置
 *是不是符合条件，如果符合则这一层的就加上，因为所有这一层是不是有符合长度的字符串
 *都已经被压缩在flag中去了，所以只要flag是真，那就是可以相加，然后逐层相加，取模
 *即可
 */
void findw(int con,char *s){
    int u = 0;
    int deep = 0;
    for(; *s; s++){
        int v = *s - 'a';
        if(ch[u][v]){
            deep ++;
            u = ch[u][v];
            ans[con+deep] = (ans[con]*flag[u] + ans[con+deep])%MOD;
        }//因为要取MOD所以写成如此，不然也可以写成+=；
        else
            break;

    }
}

int main(){
    char str[300010];
    int cas = 1;
    while(~scanf("%s",str)){
        clearw();
        memset(ans,0,sizeof(ans));
        int len = strlen(str);
        ans[0] = 1;//这里非常重要，第一个一定是符合的
        int num;
        scanf("%d",&num);
        char strt[110];
        while(num--){
            scanf("%s",strt);
            insertw(strt);
        }
        for(int i = 1;i <= len;i++){
            findw(i-1,str+i-1);//因为是从最完整一个单词开始拆。
        }

        printf("Case %d: %d
",cas++,ans[len]);
    }
    return  0;
}