AC自动机建立fail树后树上DP

# include 
     
      # include 
      
       # include 
       
        # include 
        
         # include 
         
          # include 
          
           # define IL inline# define RG register# define ll long long# define Fill(a, b) memset(a, b, sizeof(a))using namespace std;IL ll Read(){ RG char c = getchar(); RG ll x = 0, z = 1; for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1; for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + c - '0'; return x * z;}const int MAXN(1010);struct AC{ int fail, ch[3], num;} tree[MAXN];int n, cnt, k, f[MAXN][MAXN], ans;char t[MAXN];queue 
           
             Q;IL void Insert(){ RG int len = strlen(t), x = 0; for(RG int i = 0; i < len; i++){ if(!tree[x].ch[t[i] - 'A']) tree[x].ch[t[i] - 'A'] = ++cnt; x = tree[x].ch[t[i] - 'A']; } tree[x].num++;}IL void Bfs(){ while(!Q.empty()) Q.pop(); for(RG int i = 0; i < 3; i++) if(tree[0].ch[i]) Q.push(tree[0].ch[i]); while(!Q.empty()){ RG int u = Q.front(); Q.pop(); for(RG int i = 0; i < 3; i++) if(tree[u].ch[i]){ tree[tree[u].ch[i]].fail = tree[tree[u].fail].ch[i]; Q.push(tree[u].ch[i]); } else tree[u].ch[i] = tree[tree[u].fail].ch[i]; tree[u].num += tree[tree[u].fail].num; }}int main(){ n = Read(); k = Read(); for(RG int i = 1; i <= n; i++){ scanf(" %s", t); Insert(); } Bfs(); Fill(f, -127); f[0][0] = 0; for(RG int K = 1; K <= k; K++){ for(RG int i = 0; i <= cnt; i++) for(RG int j = 0; j < 3; j++) f[K][tree[i].ch[j]]=max(f[K][tree[i].ch[j]],f[K - 1][i] + tree[tree[i].ch[j]].num); } for(RG int i = 0; i <= cnt; i++) ans = max(ans, f[k][i]); printf("%d\n", ans); return 0;}