input
字符串s 1<=len(s)<=300000
n 1<=n<=4000
word1
word2
...
wordn
1<=len(wordi)<=100
output
由一个或多个word拼成s的种数％20071027.
做法１：dp:单词长度最多为100,d[i]表示到第i个字符结束的种数，则如果d[j]到d[i]这段字符能从trie中找到,d[i]+=d[j],i-100<j<=i
//1225ms
#include <cstdio>
#include <queue>
#include <cstring>
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <cctype>
#define MAX 100000
#define LL long long
#define mod 20071027
struct trie
{
int ch[*MAX][];
bool val[*MAX];
int sz;
trie()
{
sz=;
memset(ch[],,sizeof(ch[]));
}
int idx(char &c) { return c-'a';}
char* insert(char*s)
{
int u=;
for(;*s;s++)
{
int c=idx(*s);
if(!ch[u][c])
{
memset(ch[sz],,sizeof(ch[sz]));
val[sz]=;
ch[u][c]=sz++;
}
u=ch[u][c];
}
val[u]=;
return s;
}
int find(char*s,int n)
{
int u=;
for(int i=;i<n;i++)
{
int c=idx(s[i]);
if(!ch[u][c]) return ;
u=ch[u][c];
}
return val[u];
}
};
trie t;
char s[*MAX+],word[];
int n,maxl,d[*MAX+],cas=;
int main()
{
//freopen("/home/user/桌面/in","r",stdin);
while(scanf("%s",s)==)
{
memset(t.ch[],,sizeof(t.ch[]));
t.sz=;
scanf("%d",&n);
maxl=;
while(n--)
{
scanf("%s",word);
int l=t.insert(word)-word;
maxl=std::max(maxl,l);
}
n=strlen(s);
memset(d,,sizeof(d));
int u=,work=;
for(int i=;i<maxl;i++)
{
int c=t.idx(s[i]);
if(!t.ch[u][c]) break;
u=t.ch[u][c];
if(t.val[u])
{
work=;
d[i]=;
}
}
// for(int i=0;i<=n;i++) printf("%d ",d[i]);printf("\n");
if(work)
{
for(int i=;i<n;i++)
{
for(int j=;j<=maxl;j++)
{
if(i-j>=&&t.find(s+i-j+,j)) d[i]=(d[i]+d[i-j])%mod;
}
}
}
// for(int i=0;i<=n;i++) printf("%d ",d[i]);printf("\n");
printf("Case %d: %d\n",cas++,d[n-]);
}
//printf("time=%.3lf",(double)clock()/CLOCKS_PER_SEC);
return ;
}
dp
做法２：直接模拟：一开始只有一条路找，每个单词结束时分出一条路从头开始
//79ms
#include <cstdio>
#include <queue>
#include <cstring>
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <cctype>
#define MAX 100000
#define LL long long
#define mod 20071027
struct trie
{
int ch[*MAX][];
bool val[*MAX];
int sz;
trie()
{
sz=;
memset(ch[],,sizeof(ch[]));
}
int idx(char &c) { return c-'a';}
void insert(char*s)
{
int u=;
for(;*s;s++)
{
int c=idx(*s);
if(!ch[u][c])
{
memset(ch[sz],,sizeof(ch[sz]));
val[sz]=;
ch[u][c]=sz++;
}
u=ch[u][c];
}
val[u]=;
}
};
trie t;
char s[*MAX+],word[];
int n,cas=,head[][],count[][],num[];
int main()
{
//freopen("/home/user/桌面/in","r",stdin);
while(scanf("%s",s)==)
{
memset(t.ch[],,sizeof(t.ch[]));
t.sz=;
scanf("%d",&n);
while(n--)
{
scanf("%s",word);
t.insert(word);
}
int d=;
num[d]=;
head[d][]=;
count[d][]=;
for(char*p=s;*p;p++,d^=)
{
// printf("%d %d\n",count[d][0],d);
int &idx=num[d^]=;
int c=t.idx(*p);
head[d^][]=;
count[d^][]=;
for(int i=;i<num[d];i++)
{
int &f=head[d][i];
if(t.ch[f][c])//继续走到下一个字母
{
if(t.val[t.ch[f][c]])//走完一个单词,从头开始,总是head[d][0]
{
count[d^][]+=count[d][i];
count[d^][]%=mod;
}
head[d^][idx]=t.ch[f][c];
count[d^][idx++]=count[d][i];
}
}
}
// printf("%d %d\n",count[d][0],d);
printf("Case %d: %d\n",cas++,count[d][]);
}
//printf("time=%.3lf",(double)clock()/CLOCKS_PER_SEC);
return ;
}
模拟