题意:
给你一个由N个单词组成的词典，和一个字符串S。问你S由N中的单词组成的方法有多少种?字典中的单词可以重复使用但是不可重叠。
分析:
令d[i] = x 表示S串的后缀[i,L-1]串有多少种构造方式.L = strlen(S).字符从0到L-1下标.
d[i] = sum(d[i+len(x)]) 仅当[i,len(x-1)]区间正好是字典中的一个单词.
初始化:d[L] = 1. 最后求得d[0]即为所求答案.
为什么要倒着求?要运用Trie树,如果正着求.求d[5]的话,暴力的去扫0,4,去看他们到5是否是字典中的字符串.每次共调用5次find函数.显然倒着能够更好地运用Trie树.
#include<bits/stdc++.h>
#include<cstdio>
#include<iostream>using namespace std;
const int maxn = 4e5+1111;struct node
{int ch[maxn][26];int v[maxn];int sz;void init(){sz=1;memset(ch[0],0,sizeof ch[0]);}int idx(char c){return c-'a';}void insert(char *s){int u=0,n=strlen(s);for(int i=0;i<n;i++){int id=idx(s[i]);if(ch[u][id]==0){ch[u][id]=sz;memset(ch[sz],0,sizeof ch[sz]);v[sz++]=0;}u=ch[u][id];}v[u]=n;///v存放长度}void find(char *s,int len,vector<int>&vc){int u=0;for(int i=0;i<len;i++){int id=idx(s[i]);if(ch[u][id]==0)return;u=ch[u][id];///if(v[u])vc.push_back(v[u]);}}
};node trie;
const int mod=20071027;
char s[300000+111],word[1111];
int d[300000+111];
int main()
{int kase=1;while(~scanf("%s",s)){int w;cin>>w;trie.init();for(int i=0;i<w;i++){scanf("%s",word);trie.insert(word);}memset(d,0,sizeof d);int l=strlen(s);d[l]=1;for(int i=l-1;i>=0;i--){vector<int>vc;trie.find(s+i,l-i,vc);for(int j=0;j<vc.size();j++){d[i]=(d[i]+d[ i+vc[j] ])%mod;}}printf("Case %d: %d\n",kase++,d[0]);}}