UVa 1401 Remember the Word (Trie树模板题)
阿里云国内75折 回扣 微信号:monov8 |
阿里云国际,腾讯云国际,低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号:monov8 飞机:@monov6 |
递推写法:
L = strlen(text);
for (i = L - 1; i >= 0; --i)
{
trie.find_prefixes(text + i, L - i, p);
for (j = 0; j < p.size(); ++j)
cnt[i] = (cnt[i] + cnt[i + len[p[j]]]) % MOD; ///倒着递推
}
完整代码:
/*0.112s*/
#include<bits/stdc++.h>
using namespace std;
const int maxnode = 4000 * 100 + 5; /// trie树节点上限 = maxw * maxwl
const int sigma_size = 26;
const int maxl = 300000 + 5; /// 文本串最大长度
const int maxw = 4000 + 5; /// 单词最大个数
const int maxwl = 100 + 5; /// 每个单词最大长度
const int MOD = 20071027;
struct Trie
{
int ch[maxnode][sigma_size]; /// ch[node_id][nextchar]表示第id号节点下的节点对应的id号
int val[maxnode];
int sz; /// 结点总数
void clear() { sz = 1; memset(ch[0], 0, sizeof(ch[0])); } /// 初始时只有一个根结点
/// 插入字符串s,附加信息为v。注意v必须非0,因为0代表“本结点不是单词结点”
void insert(const char *s, int v)
{
int u = 0, n = strlen(s), c;
for (int i = 0; i < n; ++i)
{
c = s[i] - 'a';
if (ch[u][c] == 0) /// 结点不存在
{
memset(ch[sz], 0, sizeof(ch[sz]));
val[sz] = 0; /// 中间结点的附加信息为0
ch[u][c] = sz++; /// 新建结点
}
u = ch[u][c]; /// 往下走
}
val[u] = v; /// 字符串的最后一个字符的附加信息为v
}
/// 找字符串s的前缀(前缀长度<=len)
void find_prefixes(const char *s, int len, vector<int>& ans)
{
int u = 0, c;
for (int i = 0; s[i] && i < len; ++i)
{
c = s[i] - 'a';
if (ch[u][c] == 0) break;
u = ch[u][c];
if (val[u]) ans.push_back(val[u]); /// 找到一个前缀
}
}
} trie;
int cnt[maxl], len[maxw], S;
char text[maxl], word[maxwl];
int main()
{
int t = 0, i, j, L;
vector<int> p;
while (gets(text))
{
L = strlen(text);
scanf("%d", &S);
getchar();
trie.clear();
for (i = 1; i <= S; ++i)
{
gets(word);
len[i] = strlen(word);
trie.insert(word, i);
}
memset(cnt, 0, sizeof(cnt));
cnt[L] = 1;
for (i = L - 1; i >= 0; --i)
{
p.clear();
trie.find_prefixes(text + i, L - i, p);
for (j = 0; j < p.size(); ++j)
cnt[i] = (cnt[i] + cnt[i + len[p[j]]]) % MOD;///倒着递推
}
printf("Case %d: %d\n", ++t, cnt[0]);
}
return 0;
}
阿里云国内75折 回扣 微信号:monov8 |
阿里云国际,腾讯云国际,低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号:monov8 飞机:@monov6 |