题目大意：给定有ABC组成的串n个，然后请你生成一个长度为K的串求给定的串在生成串中最多被匹配时的次数

输入

3 7

ABA

CB

ABACB

输出：

4

题目解析：这道题目就是对于每一个节点每次处理下一个（第N+1）个是什么字母，然后每次匹配确定当前字符一定有用（一定存在下一个模式串）然后进行匹配的同时进行DP就行了（保证每个节点到根的串被匹配否则不就浪费长度了么。。）

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;#define rep(i,k) for(int (i)=1;(i)<=(k);(i)++)#define repz(i,k) for(int (i)=0;(i)<(k);(i)++)const int MAXN = 20;const int MAXK = 1000;struct State{    int fail, flag;    int ch[3];}p[MAXN*15+30];int scnt, Bef[MAXN*15+30];void Add(char *s){    int now = 0, len = strlen(s);    repz(i, len){        if(!p[now].ch[s[i]-'A'])            p[now].ch[s[i]-'A'] = ++scnt;        now = p[now].ch[s[i]-'A'];    }    p[now].flag++;}void _initTree(){    queue
         
           que; repz(i, 3) if(p[0].ch[i]) que.push(p[0].ch[i]); while(!que.empty()){ int u = que.front(); que.pop(); repz(i, 3) if(p[u].ch[i]){ int v = p[u].ch[i]; que.push(v); int k = p[u].fail; while(k && !p[k].ch[i]) k = p[k].fail; p[v].fail = p[k].ch[i]; Bef[v] = p[p[v].fail].flag > 0 ? p[v].fail : Bef[p[v].fail]; } }}int dp[MAXK+10][MAXN*15+30];void match(int len){ memset(dp, -1, sizeof dp); dp[0][0] = 0; queue
          
           
             > que; que.push(make_pair(0, 0)); pair
            
              tmp; while(!que.empty()){ tmp = que.front(); que.pop(); int u = tmp.first; int ru = u, i = tmp.second; if(i == len) break; repz(ids, 3){ u = ru; if(p[u].ch[ids]) u = p[u].ch[ids]; else{ int k = p[u].fail; while(k && !p[k].ch[ids]) k = p[k].fail; u = p[k].ch[ids]; } if(!u) continue; int k = u, sum = 0; while(k){ sum += p[k].flag; k = Bef[k]; } if(dp[i][ru] + sum > dp[i+1][u]){ dp[i+1][u] = dp[i][ru] + sum; que.push(make_pair(u, i+1)); } } } int ans = 0; scnt++; repz(i, scnt) ans = max(ans, dp[len][i]); printf("%d\n", ans);}int main(){ int n, k; char s[40]; scanf("%d%d", &n, &k); rep(i, n){ scanf("%s", s); Add(s); } _initTree(); match(k); return 0;}