BZOJ 2580 Video Game

发表于 | 更新于

Link

Solution

在每个节点上记录f[i]f[i]表示长度为ii的串匹配到当前节点的最大匹配数，更新后继节点的值即可。

Tips

初始值的设置要仔细考虑。

Code

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
//Code by Lucida
#include<bits/stdc++.h>
//#define get(x) scanf("%d",&x)
//#define debug(x) std::cout<<#x<<'='<<x<<std::endl
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
const int MAXN=1000+10,INF=0x1f1f1f1f;
using std::fill_n;
namespace AC
{
	const char SB='A',SE='C';
	const int SIGMA=SE-SB+1;
	const int SIZE=20*20;
	struct Node
	{
		Node *son[SIGMA],*fail,*last;
		int cnt,f[MAXN];
		Node *&next(char c){return son[c-SB];}
		Node()
		{
			memset(son,0,sizeof(son));
			fail=last=0;cnt=0;
			fill_n(f,sizeof(f)/sizeof(f[0]),-INF);
		}
	}*root=new Node,*POOL=(Node*)malloc(SIZE*sizeof(Node)),*ME=POOL;
	Node *newNode(){return new(ME++) Node;}
	void Insert(char *s)
	{
		Node *cur=root;
		for(int i=1,L=strlen(s+1);i<=L;i++)
		{
			if(!cur->next(s[i])) cur->next(s[i])=newNode();
			cur=cur->next(s[i]);
		}
		cur->cnt++;
	}
	Node *Q[SIZE];int he,ta;
	void Build()
	{
		he=1,ta=0;	
		root->fail=root;
		for(char c=SB;c<=SE;++c)
			if(!root->next(c)) root->next(c)=root;
			else
			{
				root->next(c)->fail=root;
				Q[++ta]=root->next(c);
			}
		while(he<=ta)
		{
			Node *cur=Q[he++];
			for(char c=SB;c<=SE;++c)
			{
				Node *&son=cur->next(c);
				if(!son) son=cur->fail->next(c);
				else
				{
					son->fail=cur->fail->next(c);
					son->last=son->fail->cnt?son->fail:son->fail->last;
					if(son->last) son->cnt+=son->last->cnt;
					Q[++ta]=son;
				}
			}
		}
	}
	int DP(int K)
	{
		int res=0;
		root->f[0]=0;
		for(int i=1;i<=K;i++)
		{
			Q[he=ta=1]=root;
			while(he<=ta)
			{
				Node *cur=Q[he++];
				for(char c=SB;c<=SE;++c)
				{
					Node *&son=cur->next(c);
					if(son->f[i]==-INF)
					{
						Q[++ta]=son;
						son->f[i]++;
					}
					chkmx(son->f[i],cur->f[i-1]+son->cnt);
					if(i==K) chkmx(res,son->f[K]);
				}
			}
		}//f[k] f[i]
		return res;
	}
}
using namespace AC;
int main()
{
	freopen("input","r",stdin);
	static char s[MAXN];
	int n,K;get(n),get(K);
	for(int i=1;i<=n;i++)
		scanf("%s",s+1),Insert(s);
	Build();
	printf("%d\n",DP(K));
	return 0;
}
/* AC Record(Bugs) *
 * RE the -1 at 74 isn't sure to be covered. 
 * * * * * * * * * */