题目大意:一个字符串,可以分解成若干英语单词的连接(单词可以重复使用),求有多少种方法?
#include<iostream> #include<cstdio> #include<cstring> #include<vector> using namespace std; const int maxl=300005; const int maxwn=4005; const int maxwl=105; const int MOD=20071027; const int maxnode=400005; const int sigma_size=26; struct Trie { int ch[maxnode][sigma_size]; int val[maxnode]; int sz; void clear(){sz=1;memset(ch[0],0,sizeof(ch[0]));} int idx(char c){ return c-'a'; } void insert(const char *s,int v) { int i,c,u=0,n=strlen(s); for(i=0;i<n;i++) { 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]=v; } void find_prefixes(const char *s,int len,vector<int> &ans) { int i,c,u=0; for(i=0;i<len;i++) { if(s[i]=='