View Code
1 #include<cstdio>
2 #include<cstring>
3 #include<stdlib.h>
4 #define N 1010
5 struct node
6 {
7 node *next[
26];
8 node *
fail;
9 int count,index;
10 node()
11 {
12 count=
0,index=
0,fail=
NULL;
13 for(
int i=
0;i<
26;i++)next[i]=
NULL;
14 }
15 }*root,*q[
501000];
16 int head,tail;
17 int n,m,w,sum,x[N],y[N];
18 char map[N][N];
19 char str[N],dir[N];
20 int len[N];
21 int h[
8]={-
1,-
1,
0,
1,
1,
1,
0,-
1};
22 int c[
8]={
0,
1,
1,
1,
0,-
1,-
1,-
1};
23 void insert(
int ii)
24 {
25 int i=
0,index;
26 node *temp=
root;
27 len[ii]=
strlen(str);
28 while(str[i])
29 {
30 index=str[i]-
'A';
31 if(temp->next[index]==NULL)temp->next[index]=
new node();
32 temp=temp->
next[index];
33 i++
;
34 }
35 temp->count=
1;
36 temp->index=
ii;
37 }
38 void build_ac()
39 {
40 node *temp,*
p;
41 head=tail=
0;
42 q[head++]=
root;
43 while(head!=
tail)
44 {
45 temp=q[tail++
];
46 for(
int i=
0;i<
26;i++
)
47 {
48 if(temp->next[i]!=
NULL)
49 {
50 if(temp==root)temp->next[i]->fail=
root;
51 else
52 {
53 p=temp->
fail;
54 while(p!=
NULL)
55 {
56 if(p->next[i]!=
NULL)
57 {
58 temp->next[i]->fail=p->
next[i];
59 break;
60 }
61 p=p->
fail;
62 }
63 if(p==NULL)temp->next[i]->fail=
root;
64 }
65 q[head++]=temp->
next[i];
66 }
67 }
68 }
69 }
70 bool Is_OK(
int x,
int y)
71 {
72 if(x>=n||x<
0||y<
0||y>=
m)
73 return false;
74 return true;
75 }
76 void query(
int i,
int j,
int k)
77 {
78 int cx=i,cy=
j,ind;
79 node *temp=root,*
p;
80 for(;Is_OK(cx,cy);cx+=h[k],cy+=
c[k])
81 {
82 ind=map[cx][cy]-
'A';
83 printf(
"%d\n",ind);
84 while(temp->next[ind]==NULL&&temp!=
root)
85 {
86 temp=temp->
fail;
87
88 }
89 temp=temp->
next[ind];
90 p=(temp==NULL)?
root:temp;
91 while(p!=
root)
92 {
93 if(p->
count)
94 {
95 sum++
;
96 p->count=
0;
97 x[p->index]=cx-(h[k]*len[p->
index]);
98 y[p->index]=cy-(c[k]*len[p->
index]);
99 dir[p->index]=
'A'+
k;
100 }
101 p=p->
fail;
102 }
103 }
104 }
105 void solution()
106 {
107 for(
int i=
0;i<n&&sum<w;i++
)
108 {
109 query(i,
0,
1);query(i,
0,
2);query(i,
0,
3);
110 query(i,m-
1,
5);query(i,m-
1,
6);query(i,m-
1,
7);
111 }
112 for(
int i=
0;i<m&&sum<w;i++
)
113 {
114 query(
0,i,
3);query(
0,i,
4);query(
0,i,
5);
115 query(n-
1,i,
0);query(n-
1,i,
1);query(n-
1,i,
7);
116 }
117 }
118 int main()
119 {
120 while(~scanf(
"%d%d%d",&n,&m,&
w))
121 {
122 root=
new node();
123 for(
int i=
0;i<n;i++
)
124 scanf(
"%s",map[i]);
125 sum=
0;
126 for(
int i=
0;i<w;i++
)
127 {
128 scanf(
"%s",str);
129 insert(i+
1);
130 }
131 build_ac();
132 solution();
133 for(
int i=
1;i<=w;i++
)
134 printf(
"%d %d %c\n",x[i],y[i],dir[i]);
135
136 }
137 return 0;
138 }
题意：
告诉你一篇文章，也就是一个nxm的字符矩阵，然后给你w个单词，问这些单词在文章中出现的位置，输出坐标，然后现在有八个方向。
同时还要在输出的坐标位置后面输出相应的匹配方向。
为了节省时间，我们肯定首先要建立一个字典树。
然后做法有两种，一种是直接从文章中的每一个点出发从八个方向，在字典树当中比较。
一种是建立ac自动机，构建字典树当中的fail指针，从文章的边界出发，将所有的能匹配的方向都扫一遍就ok了。。。
字典树做法：
View Code
1 #include<cstdio>
2 #include<cstring>
3 #define N 1010
4 struct node
5 {
6 node *next[
26];
7 int count,index;
8 node()
9 {
10 count=
0,index=
0;
11 for(
int i=
0;i<
26;i++)next[i]=
NULL;
12 }
13 }*
root;
14 char map[N][N];
15 char str[N];
16 int n,m,w,sum;
17 int x[N],y[N];
18 char dir[N];
19 int h[
8]={-
1,-
1,
0,
1,
1,
1,
0,-
1};
20 int c[
8]={
0,
1,
1,
1,
0,-
1,-
1,-
1};
21 void insert(
int ii)
22 {
23 node *p=
root;
24 int i=
0;
25 while(str[i])
26 {
27 int ind=str[i]-
'A';
28 if(p->next[ind]==NULL)p->next[ind]=
new node();
29 p=p->
next[ind];
30 i++
;
31 }
32 p->count=
1;
33 p->index=
ii;
34 }
35 bool Is_OK(
int x,
int y)
36 {
37 if(x>=
0&&x<n&&y>=
0&&y<
m)
38 return true;
39 return false;
40 }
41 void query(
int i,
int j,
int k)
42 {
43 int cx=i,cy=
j,index;
44 node *temp=root,*
p;
45 for(;Is_OK(cx,cy);cx+=h[k],cy+=
c[k])
46 {
47 index=map[cx][cy]-
'A';
48 if(temp->next[index]==
NULL)
49 return ;
50 temp=temp->
next[index];
51 if(temp->
count)
52 {
53 sum++
;
54 x[temp->index]=
i;
55 y[temp->index]=
j;
56 dir[temp->index]=
'A'+
k;
57 temp->count=
0;
58 }
59 }
60 }
61 void solution()
62 {
63 for(
int i=
0;i<n;i++
)
64 {
65 for(
int j=
0;j<m;j++
)
66 {
67 for(
int k=
0;k<
8;k++
)
68 {
69 query(i,j,k);
70 if(sum==w)
break;
71 }
72 if(sum==w)
break;
73 }
74 if(sum==w)
break;
75 }
76 }
77 int main()
78 {
79 while(~scanf(
"%d%d%d",&n,&m,&
w))
80 {
81 root=
new node();
82 for(
int i=
0;i<n;i++
)
83 scanf(
"%s",map[i]);
84 for(
int i=
0;i<w;i++
)
85 {
86 scanf(
"%s",str);
87 insert(i+
1);
88 }
89 sum=
0;
90 solution();
91 for(
int i=
1;i<=w;i++
)
92 printf(
"%d %d %c\n",x[i],y[i],dir[i]);
93 }
94 return 0;
95 }
ac自动机:
转载于:https://www.cnblogs.com/nuoyan2010/archive/2013/03/02/2939930.html
相关资源：JAVA上百实例源码以及开源项目
