Trie树基础题，记录下代码。
#include#include #define MaxNode 4005*100#define NodeSize 26#define MOD 20071027char givenword[300005];int ans[300005];int next[MaxNode][NodeSize];class Trie{ public: int val[MaxNode]; int sz; Trie(){ sz = 1; //初始时有一个根结点 memset(next[0], 0, sizeof(next[0])); } int idx(char ch){ return ch - 'a'; } void insert(char *s, int v){ int len = strlen(s); int d = 0; for(int i = 0; i < len; ++i){ int _idx = idx(s[i]); if(!next[d][_idx]){ memset(next[sz],0,sizeof(next[sz])); val[sz] = 0; next[d][_idx] = sz++; } d = next[d][_idx]; } val[d] = v; } void query(char *s,int pos){ int len = strlen(s); int d = 0; for(int i = 0; i < len; ++i){ int _idx = idx(s[i]); if(!next[d][_idx]) return; d = next[d][_idx]; if(val[d]){ ans[pos] += ans[pos+i+1]; if(ans[pos] > MOD) ans[pos] -= MOD; } } return; }};int main(){ int S; int Case = 1; while(scanf("%s",givenword)!=EOF){ int len = strlen(givenword); memset(ans,0,(len+1)*sizeof(int)); ans[len] = 1; scanf("%d",&S); char tstr[105]; Trie trie; for(int i = 0;i < S;++i){ scanf("%s",tstr); trie.insert(tstr,1); } for(int i = len-1; i >= 0; --i){ trie.query(&givenword[i],i); } printf("Case %d: ",Case++); printf("%d\n",ans[0]); } return 0;}