BZOJ 2462 矩阵模板

发表于 | 更新于

Link

Solution

枚举每个小矩阵，依次把每行加入Trie，建立AC自动机。 用大矩阵的每一行去匹配小矩阵，如果匹配成功了，就可以计算出相应矩阵左上角的座标。

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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
//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;
using std::vector;

namespace AC
{
	const int SIZE=MAXN*MAXN;	
	struct Node
	{
		Node *son[2],*fail,*last;
		vector<int> match;
		Node *&next(char c){return son[c-'0'];}
	}*root,POOL[SIZE],*ME=POOL;//[MAXN];
	Node *newNode()
	{
		static Node *cur;
		cur=ME++;cur->match.clear();cur->son[0]=cur->son[1]=cur->fail=cur->last=0;
		return cur;
	}
	void Insert(char *s,int l)
	{
		if(!root) root=newNode();
		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->match.push_back(l);
	}
	void Build()
	{
		static Node *Q[SIZE];
		static int hd,ta;
		hd=1,ta=0;
		for(char c='0';c<='1';++c)
		{
			Node *&son=root->next(c);
			if(!son) son=root;
			else
			{
				son->fail=root;
				son->last=0;
				Q[++ta]=son;
			}
		}
		while(hd<=ta)
		{
			Node *cur=Q[hd++];
			for(char c='0';c<='1';c++)
			{
				Node *&son=cur->next(c);
				if(!son) son=cur->fail->next(c);
				else
				{
					son->fail=cur->fail->next(c);
					son->last=son->fail->match.size()?son->fail:son->fail->last;
					Q[++ta]=son;
				}
			}
		}
	}
}
using namespace AC;
int A[MAXN][MAXN],a,b;
void Clear()
{
	ME=POOL;
	root=0;
	memset(A,0,sizeof(A));
}
void DFS(Node *pos,int x,int y)
{
	for(int i=0;i<pos->match.size();i++)
	{
		int u=pos->match[i];
		if(x-u+1>=1 && y-b+1>=1) A[x-u+1][y-b+1]++;
	}
	if(pos->last) DFS(pos->last,x,y);
}
int main()
{
	static char mtrx[MAXN][MAXN],str[MAXN];
	int n,m;get(n),get(m),get(a),get(b);
	for(int i=1;i<=n;i++)
		scanf("%s",mtrx[i]+1);
	int Q;get(Q);
	while(Q--)
	{
		Clear();
		for(int i=1;i<=a;i++)
		{
			scanf("%s",str+1);
			Insert(str,i);
		}
		Build();
		for(int i=1;i<=n;i++)
		{
			Node *cur=root;
			for(int j=1;j<=m;j++)
			{
				cur=cur->next(mtrx[i][j]);
				if(cur->match.size()) DFS(cur,i,j);
				else if(cur->last) DFS(cur->last,i,j);
			}
		}
		int matched=0;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				if(A[i][j]>=a)
				{
					matched=1;
					break;
				}
		printf("%d\n",matched);
	}
	return 0;
}
/* AC Record(Bugs) *
 * RE sizeof queue is to small 
 * * * * * * * * * */