HDU6086 Rikka with String

2017多校, AC自动机, DP

　　2017 Multi-University Training Contest 5

　　题意：给定n个01模式串，求一个长度为2L、覆盖全部模式串的反对称(对于任意x，每一个对称位置都不同)主串的个数。 - 原题链接

　　对于每个模式串，它在主串中可能有这样一些情况：

  • 出现在左串，此时展示出来的是原串
  • 出现在右串，与此相对应的，左串里一定有它的反对称串

　　那我们把每个串的原串和反对称串同时插入AC自动机中，只需要处理长度为L的串。还有一种情况是模式串横跨左右两串，此时需要特殊处理哪些点可以作为串终点。 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<queue>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=1024+10, DEF=0x8f8f8f8f;
int n, m, rt, tot, val[maxn];
bool f[2][maxn][maxn];
struct node
{
	int nxt[4], fail, st;
	void Init()
	{
		fail=st=0;
		memset(nxt, 0, sizeof nxt);
		return ;
	}
}tr[maxn];
int getch(char c)
{
	if(c=='A')	return 0;
	if(c=='T')	return 1;
	if(c=='G')	return 2;
	return 3;
}
void Insert(int rt, int k, char *ch)
{
	for(int i=0, len=strlen(ch), cur; i<len; i++)
	{
		cur=getch(ch[i]);
		if(!tr[rt].nxt[cur])
		{
			tr[++tot].Init();
			tr[rt].nxt[cur]=tot;
		}
		rt=tr[rt].nxt[cur];
	}
	tr[rt].st|=(1<<k);
	return ;
}
void Build(int rt)
{
	queue<int> q;
	q.push(rt);
	while(!q.empty())
	{
		int now=q.front(), p=0;
		q.pop();
		for(int i=0; i<4; i++)
		{
			if(!tr[now].nxt[i])	tr[now].nxt[i]=tr[tr[now].fail].nxt[i];
			else
			{
				p=tr[now].nxt[i];
				q.push(p);
				if(now)	tr[p].fail=tr[tr[now].fail].nxt[i];
				tr[p].st|=tr[tr[p].fail].st;
			}
		}
	}
	return ;
}
int Cal(int st)
{
	int cnt=0;
	for(int i=0; i<n; i++) if(st&(1<<i))	cnt+=val[i];
	return cnt;
}
int Work()
{
	memset(f, 0, sizeof f);
	f[0][0][0]=1;
	
	int lim=1<<n, u=0, ans=DEF;
	for(int i=1; i<=m; i++)
	{
		u^=1;
		memset(f[u], 0, sizeof f[u]);
		for(int j=0; j<=tot; j++)
			for(int k=0; k<lim; k++)
				for(int h=0; h<4; h++)
					f[u][tr[j].nxt[h]][k|tr[tr[j].nxt[h]].st]|=f[u^1][j][k];
	}
	for(int i=0; i<=tot; i++)
		for(int j=0; j<lim; j++) if(f[u][i][j])
			ans=max(ans, Cal(j));
	return ans;
}
int main()
{
	while(scanf("%d%d", &n,  &m)!=EOF)
	{
		rt=0, tot=0;
		tr[rt].Init();
		
		char s[maxn];
		for(int i=0; i<n; i++)
		{
			scanf("%s%d", s, &val[i]);
			Insert(rt, i, s);
		}
		Build(rt);
		
		int ans=Work();
		ans<0 ? printf("No Rabbit after 2012!\n") : printf("%d\n", ans);
	}
	return 0;
}