一个数组开小了一点点，一直提示wa，郁闷，这题比上个题简单一点。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#include <algorithm>
#include <cstdlib>
using namespace std;
#define N 1001
#define INF 1000000
int trie[N][];
int que[N];
int o[<<];
int flag[N];
int fail[N];
int dp1[N][<<];
int dp2[N][<<];
int t,n;
int lowbit(int t)
{
return t&(-t);
}
void CL()
{
t = ;
memset(trie,-,sizeof(trie));
memset(o,,sizeof(o));
memset(flag,,sizeof(flag));
}
int judge(char s)
{
switch(s)
{
case'A':
return ;
case'C':
return ;
case'G':
return ;
case'T':
return ;
}
return ;
}
void insert(char *str,int x,int j)
{
int i,len,root;
root = ;
len = strlen(str);
for(i = ; i < len; i ++)
{
if(trie[root][judge(str[i])] == -)
trie[root][judge(str[i])] = t ++;
root = trie[root][judge(str[i])];
}
flag[root] = <<j;
}
void build_ac()
{
int head,tail,front,i;
head = tail = ;
for(i = ; i < ; i ++)
{
if(trie[][i] != -)
{
fail[trie[][i]] = ;
que[tail++] = trie[][i];
}
else
{
trie[][i] = ;
}
}
while(head != tail)
{
front = que[head++];
flag[front] |= flag[fail[front]];
for(i = ; i < ; i ++)
{
if(trie[front][i] != -)
{
que[tail++] = trie[front][i];
fail[trie[front][i]] = trie[fail[front]][i];
}
else
{
trie[front][i] = trie[fail[front]][i];
}
}
}
}
int main()
{
int m,i,j,u,x,len,k;
int sc[];
char str[];
while(scanf("%d%d",&n,&m)!=EOF)
{
CL();
for(i = ; i < n; i ++)
{
scanf("%s%d",str,&x);
len = strlen(str);
if(len > m)
{
i --;
n -- ;
continue;
}
sc[i] = x;
insert(str,x,i);
}
for(i = ;i < n;i ++)
o[<<i] = sc[i];
for(i = ; i < <<n;i ++)
{
o[i] = o[i-lowbit(i)] + o[lowbit(i)];
}
build_ac();
for(j = ; j < t; j ++)
{
for(k = ; k < (<<n); k ++)
{
dp1[j][k] = ;
dp2[j][k] = ;
}
}
dp1[][] = ;
for(i = ; i < m; i ++)
{
for(j = ; j < t; j ++)
{
for(k = ;k < (<<n);k ++)
{
if(dp1[j][k] == ) continue;
int temp;
for(u = ;u < ;u ++)
{
temp = k|flag[trie[j][u]];
dp2[trie[j][u]][temp] += dp1[j][k];
}
}
}
for(j = ; j < t; j ++)
{
for(k = ; k < (<<n); k ++)
{
dp1[j][k] = dp2[j][k];
dp2[j][k] = ;
}
}
}
int ans = -INF;
for(j = ;j < t;j ++)
{
for(k = ;k <(<<n);k ++)
{
if(dp1[j][k])
ans = max(ans,o[k]);
}
}
if(ans >= )
printf("%d\n",ans);
else
printf("No Rabbit after 2012!\n");
}
return ;
}