思路

简单的AC自动机上dp，暴力跳fail向子节点直接转移即可

代码

#include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;int trie[400][3],Nodecnt,mark[400],fail[400],dp[1001][400],root,k,n;char t[400];void insert(char *s,int len){    int o=root;    for(int i=1;i<=len;i++){        if(!trie[o][s[i]-'A'])            trie[o][s[i]-'A']=++Nodecnt;        o=trie[o][s[i]-'A'];    }    mark[o]++;}void build_AC(void){    queue
        
          q;    for(int i=0;i<3;i++){        if(trie[root][i]){            fail[trie[root][i]]=root;            q.push(trie[root][i]);        }    }    while(!q.empty()){        int x=q.front();        q.pop();        for(int i=0;i<3;i++){            if(trie[x][i]){                fail[trie[x][i]]=trie[fail[x]][i];                q.push(trie[x][i]);            }            else{                trie[x][i]=trie[fail[x]][i];            }        }    }}int query(void){    int ans=0;    int o=root;    for(int i=0;i<=k;i++)        for(int j=0;j<=Nodecnt;j++)            dp[i][j]=-0x3f3f3f3f;    dp[0][o]=0;    for(int i=0;i