题干：
时间限制:10000ms
单点时限:1000ms
内存限制:512MB
描述
给定一个包含N个单词的字典:{W1, W2, W3, ... WN}，其中第i个单词Wi有具有一个权值Vi。
现在小Hi要进行M次查询，每次查询包含一个前缀字符串Pi和一个后缀字符串Si。他希望知道同时以Pi为前缀并且以Si为后缀的单词中，权值最大的单词的权值是多少？
假设字典包含"hihocoder"、"hijacker"和"hiker"，权值依次是30、20和10。
那么对于查询前缀="hi"，后缀="er"，答案应为30.
输入
第一行包两个整数N和M。(1 <= N <= M)
以下N行每行包含一个只包含小写字母的字符串Wi和对应的权值Vi。
再之后M行每行包含两个字符串Pi和Si。
对于30%的数据，1 <= N, M <= 100
对于100%的数据，1 <= N, M <= 50000, 1 <= |Wi|, |Pi|, |Si| <= 10， 1 <= Vi <= 100000
输出
输出最大的权值。如果没有符合条件的单词，输出-1。
样例输入
3 2
hihocoder 30
hijacker 20
hiker 10
hi er
hihoco hocoder 样例输出
30
30 解题报告：
查询有前缀和后缀的条件，考虑固定其中一个条件；单词长度很短，在每个单词的每个前缀下再建一颗后缀字典树，在后缀字典树下维护权值。查询时，先匹配前缀，再查询后缀。
这题还有第二种方法，字典树哈希，先建同一棵字典树然后按照每个点的root当做seed去哈希，前缀与后缀用一个模数分开（这里取的1000007）map去哈希同时维护最大权值
AC代码1：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<unordered_map>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define ull unsigned long long
#define pb push_back
#define pm make_pair
using namespace std;
const int MAX = 2e6 + 5;
char s[55];
int trie[MAX][33];
int val[MAX];
int tot;
void insert(char str[],int w) {
int rt = 0,tmprt,len = strlen(str);
for(int i = 0; i<len; i++) {
int cur = str[i] - 'a';
if(!trie[rt][cur]) trie[rt][cur] = ++tot;
rt = trie[rt][cur];
//接下来建立后缀字典树
if(!trie[rt][27]) trie[rt][27] = ++tot;
tmprt = trie[rt][27];
for(int j = len-1; j>=0; j--) {
int cur = str[j] - 'a';
if(!trie[tmprt][cur]) trie[tmprt][cur] = ++tot;
tmprt = trie[tmprt][cur];
val[tmprt] =max(val[tmprt],w);
}
}
}
int ask(char str[],char qq[]) {
int res = 0,len = strlen(str),rt = 0;
for(int i = 0; i<len; i++) {
int cur = str[i] - 'a';
if(trie[rt][cur] == 0) return -1;
else rt = trie[rt][cur];
}
if(trie[rt][27] == 0) return -1;
rt = trie[rt][27];
len = strlen(qq);
for(int i = 0; i<len; i++) {
int cur = qq[i] - 'a';
if(trie[rt][cur] == 0 ) return -1;
else rt = trie[rt][cur];
}
return val[rt];
}
int main()
{
int n,m;
cin>>n>>m;
for(int w,i = 1; i<=n; i++) {
scanf("%s%d",s,&w);
insert(s,w);
}
char a[55],b[55];
while(m--) {
scanf("%s%s",a,b);
int lenb = strlen(b);
reverse(b,b+lenb);
printf("%d\n",ask(a,b));
}
return 0 ;
}
/*
1 1
aaa 2
a a
*/ 上面这份代码有几个细节：注意建树的时候tmprt和rt不能混用，需分开，第二画图一下就可以发现对每一个节点建后缀树的时候都会新建一个新的空节点（这也是写完自己花了一下图才发现的），这样有个好处，那就是不需要做繁琐的坐标运算，因为否则你的trie数组的第二维就得开26*2这么大，第一维就是1e6就行，而现在新开一个空节点当根节点，保持了代码的统一性，就相当于完全就是新建一棵字典树，代码不需要动太多，减少出错率。
还有一点，ask的时候别忘了查完前缀的时候rt=trie[rt][27]这一步、、、不然肯定GG（因为你继续搜索相当于顺着正向的字典树查下去了）
AC代码2：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<unordered_map>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define ull unsigned long long
#define pb push_back
#define pm make_pair
using namespace std;
const int MAX = 2e6 + 5;
char s[55];
int trie[MAX][26];
int Hash[MAX*20];
int tot;
void insert(char str[],int a[]) {
int rt = 0,len = strlen(str);
for(int i = 0; i<len; i++) {
int cur = str[i] - 'a';
if(!trie[rt][cur]) trie[rt][cur] = ++tot;
rt = trie[rt][cur];
a[i] = rt;
}
}
int ask(char str[]) {
int res = 0,len = strlen(str),rt = 0;
for(int i = 0; i<len; i++) {
int cur = str[i] - 'a';
if(trie[rt][cur] == 0) return -1;
else rt = trie[rt][cur];
}
return rt;
}
unordered_map<ll,int>g;
int A[55],B[55];
int main()
{
int n,m;
cin>>n>>m;
for(int w,i = 1; i<=n; i++) {
scanf("%s%d",s,&w);
insert(s,A);
int len = strlen(s);
reverse(s,s+len);
insert(s,B);
//至此，a和b数组的0~len-1都有对应的值了
for(int j = 0; j<len; j++) {
for(int k = 0; k<len; k++) {
ll HS = (ll)A[j] * 1000007 + B[k];
//Hash[int(HS%mod)] = MX(Hash[int(HS%mod)],w);//因为权值w都是正数，所以不需要像那个代码一样unorderedmap的时候分存在和不存在这一说、、、（主要是这不是迭代器而是数组。。所以都已经分配空间了）
if(!g.count(HS))g[HS]=w;
else if(w>g[HS])g[HS]=w;
}
}
}
char a[55],b[55];
while(m--) {
scanf("%s%s",a,b);
int lena = strlen(a);
int lenb = strlen(b);
reverse(b,b+lenb);
int x = ask(a);
int y = ask(b);
int ans = -1;
if(x!=-1&&y!=-1) {
ll w=(ll)x*1000007+y;
if(g.count(w))ans=g[w];
}
printf("%d\n",ans);
}
return 0 ;
}
京公网安备 11010502036488号