「AC自动机」地图匹配

评测点

Caioj1465

分析

这道题数据的话。。好像直接来自HDU,有谁知道原题请留言
然后数据中一个单词只会有一次机会,就不用考虑什么“第一个出现”之类了

从边框开始(尽量不重复)地一遍遍做AC自动机,为了方便求起始点,可以考虑倒着搜索(注意add也要倒着建)
为了记录答案,s记录的是“假如是单词的开头,就表示单词编号”。
因为是倒着的,c也要转向

「话说这道题应该是没有被覆盖的字符串的」

代码

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
//*******************定义*******************
struct Trie
{
int s,c[27],fail;
bool b;
}a[200010];
struct tans
{
int x,y,c;
}ans[200010];
//*******************实现*******************
void clean(int x)
{
a[x].s=a[x].fail=a[x].b=0;
for(int f=1;f<=26;f++) a[x].c[f]=-1;
}
char s[2010];int len;int k;
void add(int id)
{
len=strlen(s+1);
int x=0;
for(int i=len;i>=1;i--)
{
int f=s[i]-'A'+1;
if(a[x].c[f]<0)
{
a[x].c[f]=++k;
clean(k);
}
x=a[x].c[f];
}
a[x].s=id;
}
int list[50010];
void getfail()
{
int tou=1,wei=2;list[1]=0;
while(tou!=wei)
{
int x=list[tou];
for(int f=1;f<=26;f++)
{
int son=a[x].c[f];
if(son<0) continue;
if(x==0) a[son].fail=0;
else
{
int p=a[x].fail;
while(p>0 and a[p].c[f]<0) p=a[p].fail;//类似KMP的思想
a[son].fail=mymax(a[p].c[f],0);
//可能没有一个匹配,最后出来的c[i]==-1
}
list[wei++]=son;if(wei>50000) wei=1;
}
tou++;if(tou>50000) tou=1;
}
}
int n,m;
bool check(int x,int y)
{
return x>=1 and y>=1 and x<=n and y<=m;
}
const int tx[8]={-1,-1,0,1,1, 1, 0,-1};
const int ty[8]={ 0, 1,1,1,0,-1,-1,-1};
char map[1010][1010];
int solve(int x,int y,int c)
{
int p=0;
while(check(x,y))
{
int f=map[x][y]-'A'+1;
while(p>0 and a[p].c[f]<0) p=a[p].fail;
if(a[p].c[f]!=-1) p=a[p].c[f];
int k=p;
while(k!=0 and a[k].b==0)
{
if(a[k].s)//到了结尾
{
int o=a[k].s;
ans[o].x=x;
ans[o].y=y;
ans[o].c=(c+4)%8;//因为倒着找,要倒过来
}
a[k].b=1;//经过
k=a[k].fail;
}
x+=tx[c];y+=ty[c];
}
}
//*******************主函数*******************
int main(int argc, char *argv[])
{
int w;scanf("%d%d%d",&n,&m,&w);
for(int i=1;i<=n;i++) scanf("%s",map[i]+1);
clean(0);k=0;
for(int i=1;i<=w;i++)
{
scanf("%s",s+1);
add(i);
}
//计算fail
getfail();
//从边框开始(尽量不重复)
for(int i=1;i<=n;i++)
{
solve(i,1,1);solve(i,1,2);solve(i,1,3);//左边
solve(i,m,5);solve(i,m,6);solve(i,m,7);//右边
}
for(int j=1;j<=m;j++)
{
solve(1,j,3);solve(1,j,4);solve(1,j,5);//上边
solve(n,j,7);solve(n,j,0);solve(n,j,1);//下边
}
for(int i=1;i<=w;i++) printf("%d %d %c\n",ans[i].x-1,ans[i].y-1,ans[i].c+'A');
}

另外,如果你更喜欢正着搜索,就要正着add,s也放到结尾,c就不用转向了。给出不同的部分:
add函数:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void add(int id)
{
ans[id].len=strlen(s+1);
int x=0;
for(int i=1;i<=ans[id].len;i++)
{
int f=s[i]-'A'+1;
if(a[x].c[f]<0)
{
a[x].c[f]=++k;
clean(k);
}
x=a[x].c[f];
}
a[x].s=id;
}

solve函数:

1
2
3
4
5
6
7
8
if(a[k].s)//到了结尾 
{
int o=a[k].s;
ans[o].x=x-(ans[o].len-1)*tx[c];
ans[o].y=y-(ans[o].len-1)*ty[c];
ans[o].c=c;
//ans[o].c=(c+4)%8;//因为倒着找,要倒过来
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/4c6e.html
转载请注明出处,谢谢!