AC自动机+DP
#include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <queue> #include <algorithm> #include <vector> #include <cstring> #include <stack> #include <cctype> #include <utility> #include <map> #include <string> #include <climits> #include <set> #include <string> #include <sstream> #include <utility> #include <ctime> using std::priority_queue; using std::vector; using std::swap; using std::stack; using std::sort; using std::max; using std::min; using std::pair; using std::map; using std::string; using std::cin; using std::cout; using std::set; using std::queue; using std::string; using std::istringstream; using std::make_pair; using std::getline; using std::greater; using std::endl; using std::multimap; using std::deque; typedef long long LL; typedef unsigned long long ULL; typedef pair<int, int> PAIR; typedef multimap<int, int> MMAP; const int MAXN(1010); const int SIGMA_SIZE(4); const int MAXM(110); const int MAXE(300010); const int MAXH(18); const int INFI((INT_MAX-1) >> 1); const int MOD(2520); const ULL LIM(1000000000000000ull); map<char, int> mp; struct AC { int ch[MAXN][SIGMA_SIZE], f[MAXN]; int val[MAXN]; int size; inline int idx(char temp) { return mp[temp]; } void init() { memset(ch[0], 0, sizeof(ch[0])); val[0] = 0; size = 1; } void insert(char *S, int tv) { int u = 0, id; for(; *S; ++S) { id = idx(*S); if(!ch[u][id]) { memset(ch[size], 0, sizeof(ch[size])); val[size] = 0; ch[u][id] = size++; } u = ch[u][id]; } val[u] |= (1 << tv); } int que[MAXN]; int front, back; void construct() { int cur, u; front = back = 0; for(int i = 0; i < SIGMA_SIZE; ++i) if(ch[0][i]) { u = ch[0][i]; f[u] = 0; que[back++] = u; } while(front < back) { cur = que[front++]; for(int i = 0; i < SIGMA_SIZE; ++i) { u = ch[cur][i]; if(u) { f[u] = ch[f[cur]][i]; val[u] |= val[f[u]]; que[back++] = u; } else ch[cur][i] = ch[f[cur]][i]; } } } }; AC ac; bool vis[2][1010][1 << 10]; int scoer[15]; int solve(int len, int n) { int limit = (1 << n)-1; int cur = 0, last = 1; memset(vis[last], 0, sizeof(vis[last])); vis[last][0][0] = true; for(int i = 1; i <= len; ++i) { memset(vis[cur], 0, sizeof(vis[cur])); for(int j = 0; j < ac.size; ++j) for(int k = 0; k <= limit; ++k) if(vis[last][j][k]) { int u; for(int k2 = 0; k2 < SIGMA_SIZE; ++k2) { u = ac.ch[j][k2]; vis[cur][u][k|ac.val[u]] = true; } } cur ^= 1; last ^= 1; } int ans = -1; for(int i = 0; i <= limit; ++i) { bool flag = false; for(int j = 0; j < ac.size; ++j) if(vis[last][j][i]) { flag = true; break; } if(flag) { int tans = 0; for(int j = 0; j < n; ++j) if(i&(1 << j)) tans += scoer[j]; ans = max(ans, tans); } } return ans; } char str[110]; int main() { mp.insert(make_pair('A', 0)); mp.insert(make_pair('C', 1)); mp.insert(make_pair('G', 2)); mp.insert(make_pair('T', 3)); int n, len; while(~scanf("%d%d", &n, &len)) { ac.init(); for(int i = 0; i < n; ++i) { scanf("%s%d", str, scoer+i); ac.insert(str, i); } ac.construct(); int ans = solve(len, n); if(ans < 0) printf("No Rabbit after 2012!\n"); else printf("%d\n", ans); } return 0; }