题意：
给你一个母串，多个模式串及其价值，求用模式串拼接成母串（不重叠不遗漏），能获得的最大价值。
分析：
ac自动机中，在字典树上查找时，用dp,dp[i]拼成母串以i为结尾的子串，获得的最大价值，dp[i]=max(dp[i],dp[i-len]+val[tmp])。,len是模式串的长度，val[tmp]为其价值。
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
#include<iostream>
using namespace std;
const int maxnode = ;
const int sigma_size = ;
struct Trie{
int dp[];
int ch[maxnode][sigma_size];
int val[maxnode]; //该单词在模式串中出现的次数
int last[maxnode];
int f[maxnode]; //失配数组
int num[maxnode]; //该单词出现在文本串的次数
int pre[maxnode]; //该单词的前驱
int len[maxnode]; //以该单词结尾的单词长度
int Char[maxnode]; //该单词对应的字母
int road[maxnode]; //路径压缩优化 针对计算模式串出现的种数
int sz;
int Newnode()
{
val[sz] = f[sz] = last[sz] = len[sz] = num[sz] = ;
memset(ch[sz], , sizeof ch[sz]);
return sz++;
}
void init(){
sz=;
Newnode();
}
int idx(char c){ return c-'a'; }
void build(char *s,int v){
int u = ;
for(int i = , c; s[i] ;i++){
c = idx(s[i]);
if(!ch[u][c])
ch[u][c] = Newnode();
pre[ch[u][c]] = u;
Char[ch[u][c]] = s[i];
len[ch[u][c]] = len[u]+;
road[ch[u][c]] = ;
u = ch[u][c];
}
val[u] = max(val[u],v);
//num[u] = 0;
//return u;
}
void getFail(){
queue<int> q;
for(int i = ; i<sigma_size; i++)
if(ch[][i]) q.push(ch[][i]);
int r, c, u, v;
while(!q.empty()){
r = q.front(); q.pop();
for(c = ; c<sigma_size; c++){
u = ch[r][c];
if(!u)continue;
q.push(u);
v = f[r];
while(v && ch[v][c] == ) v = f[v]; //沿失配边走上去 如果失配后有节点 且 其子节点c存在则结束循环
f[u] = ch[v][c];
}
}
}
void find(char *T){
//计算模式串出现的个数：（每种多次出现算多次）
int j = ,l=strlen(T);
for(int i = , c, temp; i<l ; i++){
dp[i]=;
c = idx(T[i]);
while(j && ch[j][c]==) j = f[j];
j = ch[j][c]; temp = j;
while(temp){
if(val[temp]){
if(i-len[temp]<)
dp[i]=max(dp[i],val[temp]);
else if(dp[i-len[temp]])
dp[i]=max(dp[i],dp[i-len[temp]]+val[temp]);
}
temp = f[temp];
}
}
printf("%d\n",dp[l-]);
}
int find_kind(char *T){
//计算种数， 重复出现的不再计算(若多个询问则要在此处加for(i=0->sz)lu[i]=1;
int j = , i, c, temp,ans=;
for(i = ; T[i]; i++){
c = idx(T[i]);
while(j && ch[j][c] == ) j = f[j];
j = ch[j][c];
temp = j;
while(temp && road[temp]){
if(val[temp])
{
++ans;
val[temp] = ;
}
road[temp] = ;
temp = f[temp];
}
}
return ans;
}
}ac;
int n,v;
char T[],P[];
int main() {
while(~scanf("%s",T)){
ac.init();
scanf("%d",&n);
while(n--){
scanf("%s%d",P,&v);
ac.build(P,v);
}
ac.getFail();
ac.find(T);
}
}