给定一个模式串,有若干个单词,问是否能用若干个单词组合,组合成模式串
ICPC-2007 Asia regional - Nanjing
思路:这种有后缀类型的题目一开始还以为是后缀数组，然后仔细想了一下，后缀数组更多的是解决两个大的模式串之间产生的后缀之间的关系，而这个实际上是要把一堆小的零散的单词拼凑成一个大的模式串，所以给用第二种匹配方法．刘老师说这个超棒的
首先给明白一个递推关系，实际上我们可以直接从最后出发，命名一个dp数组,推出状态转移方程即dp[i] = dp[i +len(x)] + dp[i]
认为dp[i]实质上是为组成以i开始到总长度的组成反感,x实际上就是i到总长度这个子串的长度
那么解法就可以出来了
我们将所有出现的单词压入字典树
倒着遍历一遍,因为不限制单词重复使用,所以我们可以将所有适合的方案全部压入对应的后缀之中,然后相应修改匹配模块即可
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
using namespace std;
const int maxnode = 4000 * 100 + 10;
const int sigma_size = 26;
const int maxl = 300000 + 10;
const int maxw = 4000 + 10;
const int maxwl = 100 + 10;
const int MOD = 20071027;
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 u = 0, n = strlen(s);
for (int i = 0;i < n;i ++){
int 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 u = 0;
for (int i = 0;i < len;i ++){
if (s[i] == '\0') break;
int c = idx(s[i]);
if (!ch[u][c]) break;
u = ch[u][c];
if (val[u] != 0) ans.push_back(val[u]);
}
}
};
int d[maxl], len[maxw], S;
char text[maxl], word[maxwl];
Trie trie;
int main(){
int kase = 1;
while (~scanf("%s%d", text, &S)){
// printf("%d\n", S);
trie.clear();
for (int i = 1; i<= S;i ++){
scanf("%s", word);
len[i] = strlen(word);
trie.insert(word, i);
}
memset(d, 0, sizeof(d));
int L = strlen(text);
d[L] = 1;
for (int i = L - 1;i >= 0;i --){
vector<int> p;
trie.find_prefixes(text + i, L - i, p);
for (int j = 0;j < p.size();j ++){
d[i] = (d[i] + d[i + len[p[j]]]) % MOD;
}
}
printf("Case %d: %d\n", kase ++, d[0]);
}
return 0;
}
