题意：

给你一个母串，多个模式串及其价值，求用模式串拼接成母串（不重叠不遗漏），能获得的最大价值。

分析：

ac自动机中，在字典树上查找时，用dp,dp[i]拼成母串以i为结尾的子串，获得的最大价值，dp[i]=max(dp[i],dp[i-len]+val[tmp])。,len是模式串的长度，val[tmp]为其价值。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include
          
           using namespace std;const int maxnode = 300010;const int sigma_size = 26;struct Trie{ int dp[100010]; 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] = 0; memset(ch[sz], 0, sizeof ch[sz]); return sz++; } void init(){ sz=0; Newnode(); } int idx(char c){ return c-'a'; } void build(char *s,int v){ int u = 0; for(int i = 0, 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]+1; road[ch[u][c]] = 1; u = ch[u][c]; } val[u] = max(val[u],v); //num[u] = 0; //return u; } void getFail(){ queue
           
             q; for(int i = 0; i
            
             sz)lu[i]=1; int j = 0, i, c, temp,ans=0; for(i = 0; T[i]; i++){ c = idx(T[i]); while(j && ch[j][c] == 0) j = f[j]; j = ch[j][c]; temp = j; while(temp && road[temp]){ if(val[temp]) { ++ans; val[temp] = 0; } road[temp] = 0; temp = f[temp]; } } return ans; }}ac;int n,v;char T[100100],P[310];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); }}