题意:给出一个由S个不同的字符串组成的字典和一个长字符串,问:把这个长字符串分解成若干个字典中出现的字符串,共有几种分法。单词可以重复使用。
思路:将所有字典中的单词插入字典树中,用d[i]表示str[i]到str[n]的所有分解法数。所以有d[i]=sum(i+len(x)),其中x为str[i]为开头的字符串str[i...n],即枚举x,x={str[i]}或{str[i],str[i+1]},........或{str[i]+str[i+1]+str[i+2]+.....+str[n]}.初始化d[n+1]=1。
注意字典树每次执行完一组样例要重新初始化。
#include<cstdio>
#include<cstring>
#define MOD 2......
阅读全文