題目大意：給定有ABC組成的串n個，然后請你生成一個長度為K的串求給定的串在生成串中最多被匹配時的次數

輸入

3 7
ABA
CB
ABACB

輸出：

4

題目解析：這道題目就是對于每一個節點每次處理下一個（第N+1）個是什么字母，然后每次匹配確定當前字符一定有用（一定存在下一個模式串）然后進行匹配的同時進行DP就行了（保證每個節點到根的串被匹配否則不就浪費長度了么。。）

#include <cstdio> #include <algorithm> #include <cstring> #include <queue> #include <iostream> 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<int> 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<pair<int, int> > que;que.push(make_pair(0, 0));pair<int, int> 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; }

總結

以上是生活随笔為你收集整理的【AC自动机】[UESTC 554][USACO 2012]Video Game Combos的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。