描述
给定一个包含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
初始代码：
思路是前缀查找，找到到Now节点，在Now的每个点（需要是单词尾）向前验证是否满足后缀要求，满足则更新最大值，无则输出-1。
这样显然是超时了，保证试一试的态度写了下。
#include<cstdio> #include<cstdlib> #include<iostream> #include<algorithm> #include<cstring> #include<cmath> #include<memory> using namespace std; const int maxn=1000010; char s[maxn]; int ch[maxn][26],fa[maxn],id[maxn],num[maxn],cnt,val; int max(int a,int b){ if(a>b) return a; return b; } void insert() { int Now=0,L=strlen(s),x; for(int i=0;i<L;i++){ x=s[i]-'a'; if(!ch[Now][x]) ch[Now][x]=++cnt,fa[cnt]=Now,id[cnt]=x; Now=ch[Now][x]; } num[Now]=max(num[Now],val); } int Max; char a[20],b[20]; bool check(int Now) { int L2=strlen(b); for(int i=L2-1;i>=0;i--){ if(Now==0) return false; if(b[i]-'a'!=id[Now]) return false; Now=fa[Now]; } return true; } void dfs(int Now) { if(num[Now]) if(check(Now)) Max=max(Max,num[Now]); for(int i=0;i<26;i++) { if(ch[Now][i]) dfs(ch[Now][i]); } } void query() { int Now=0,L1=strlen(a),x; for(int i=0;i<L1;i++){ x=a[i]-'a'; if(!ch[Now][x]) { printf("-1 ");return ;} Now=ch[Now][x]; } Max=-1; dfs(Now); printf("%d ",Max); } int main() { int n,m,i,L1,L2; scanf("%d%d",&n,&m); for(i=1;i<=n;i++){ scanf("%s%d",s,&val); insert(); } for(i=1;i<=m;i++){ scanf("%s%s",a,b); L1=strlen(a);L2=strlen(b); query(); } return 0; }
改进：
既然对象是前缀和后缀，显然不需要后缀数组或者后缀自动机（二者对象是任意子串）来完成。还是考虑字典树，想个办法把后缀前缀一起查询了。
具体：
对单词abcd （权值为Val）： 它的后缀是d，cd，bcd，abcd。把它的后缀连接到前缀上，成为4个单词（其他的最多也才10个），用'#'连接（后缀数组唱用）
对应 ： d#abcd,cd#abcd,bcd#abcd,abcd#abcd，权值都为Val。
#include<cstdio> #include<cstdlib> #include<iostream> #include<algorithm> #include<cstring> #include<cmath> #include<memory> using namespace std; const int maxn=500010; char s[maxn]; int ch[maxn<<2][27],num[maxn<<2],cnt,Val; int max(int a,int b){ if(a>b) return a; return b; } void insert() { int L=strlen(s),x; for(int j=L-1;j>=0;j--){ int Now=0; for(int i=j;i<L;i++){ x=s[i]-'a'; if(!ch[Now][x]) ch[Now][x]=++cnt; Now=ch[Now][x]; } x=26; if(!ch[Now][x]) ch[Now][x]=++cnt; Now=ch[Now][x]; for(int i=0;i<L;i++){ x=s[i]-'a'; if(!ch[Now][x]) ch[Now][x]=++cnt; Now=ch[Now][x]; num[Now]=max(num[Now],Val); } } } char a[20],b[20]; void query() { int Now=0,L1=strlen(a),L2=strlen(b),x; for(int i=0;i<L2;i++){ x=b[i]-'a'; if(!ch[Now][x]) { printf("-1 ");return ;} Now=ch[Now][x]; } Now=ch[Now][26];if(!Now) { printf("-1 ");return ;} for(int i=0;i<L1;i++){ x=a[i]-'a'; if(!ch[Now][x]) { printf("-1 ");return ;} Now=ch[Now][x]; } printf("%d ",num[Now]); } int main() { int n,m,L1,L2; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ scanf("%s%d",s,&Val); insert(); } for(int i=1;i<=m;i++){ scanf("%s%s",a,b); query(); } return 0; }