刷的第二题AC自动机,这题简直了。。

用询问的串建AC自动机,然后。。。爆搜!

ACBB                  ACBB
ACCA                  A  A
ABBC        ——〉     A  C
ACBA                  ACBA

像这样,将最外面的每一个点将有可能的方向走,比如第一行第一列的A向东南走,就可以得到一个ACBA的串,然后像模板题一样,去匹配找就行了。(老实讲我还是觉得这个很不靠谱。。谁叫人家地图小。。)

小细节,我将查询的字符串反着建ACM了,假设要找ACBA,那我就把它变成ABCA,有什么好处呢?就是找这个串时,我们从最下面的A一路往上,找到最上面的A,这样就可以直接找到起始点了。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
const int dx[]={-,-,,,,,,-};
const int dy[]={,,,,,-,-,-};
struct Trie
{
bool b;
int s,w[],fail;
}tr[];int trlen;
int a[],len;
void clean(int x)
{
tr[x].s=;tr[x].b=false;tr[x].fail=;
memset(tr[x].w,,sizeof(tr[x].w));
}
void bt(int id)
{
int now=;
for(int i=;i<=len;i++)
{
int x=a[i];
if(tr[now].w[x]==)
{
tr[now].w[x]=++trlen;
clean(trlen);
}
now=tr[now].w[x];
}
tr[now].s=id;
}
int list[];
void bfs()
{
int head=,tail=;list[]=;
while(head!=tail)
{
int now=list[head];
for(int x=;x<=;x++)
{
int son=tr[now].w[x];
if(son==)continue;
if(now==)tr[son].fail=;
else
{
int p=tr[now].fail;
while(p!=&&tr[p].w[x]==)p=tr[p].fail;
tr[son].fail=max(tr[p].w[x],);
}
list[tail]=son;
tail++;if(tail==)tail=;
}
head++;if(head==)head=;
}
}
int n,m,T;
char mp[][],ss[];
struct Ans
{
int x,y,c;
}ans[];
void Find(int x,int y,int i)
{
int now=;
while(x>=&&y>=&&x<n&&y<m)
{
int j=mp[x][y]-'A'+;
while(now!=&&tr[now].w[j]==)now=tr[now].fail;
now=tr[now].w[j];
for(int k=now;k;k=tr[k].fail)
{
if(tr[k].b==false)
{
if(tr[k].s!=)
{
ans[tr[k].s].x=x;
ans[tr[k].s].y=y;
ans[tr[k].s].c=(i+)%;
}
tr[k].b=;
}
}
x+=dx[i];y+=dy[i];
}
}
int main()
{
scanf("%d%d%d",&n,&m,&T);
trlen=;clean();
for(int i=;i<n;i++)scanf("%s",mp[i]);
for(int i=;i<=T;i++)
{
scanf("%s",ss+);len=strlen(ss+);
for(int j=;j<=len;j++)a[j]=ss[len-j+]-'A'+;
bt(i);
}
bfs();
Find(,,);
Find(,m-,);
Find(n-,,);Find(n-,m-,);
for(int j=;j<m;j++)
{
Find(,j,);Find(,j,);Find(,j,);
Find(n-,j,);Find(n-,j,);Find(n-,j,);
}
Find(,,);Find(n-,,);
Find(,m-,);Find(n-,m-,);
for(int i=;i<n;i++)
{
Find(i,,);Find(i,,);Find(i,,);
Find(i,m-,);Find(i,m-,);Find(i,m-,);
}
for(int i=;i<=T;i++)
printf("%d %d %c\n",ans[i].x,ans[i].y,ans[i].c+'A');
return ;
}

最新文章

  1. Express 教程 01 - 入门教程之经典的Hello World
  2. yii2.0 Activeform表单部分组件使用方法
  3. {Reship}{KMP字符串匹配}
  4. Java中 final static super this instanceof 关键字用法
  5. [CareerCup] 15.5 Denormalization 逆规范化
  6. HashedWheelTimer
  7. gdb调试SAPI方式的php
  8. Spring之SpringMVC前端控制器DispatcherServlet(源码)分析
  9. ubuntu14.04下安装有道词典
  10. [js高手之路] es6系列教程 - 箭头函数详解
  11. java什么叫线程安全?什么叫不安全?
  12. 【心得】Lattice Diamond 后端约束实战小结
  13. STL的基本操作指令
  14. Android播放功能的实现
  15. Moving Tables---(贪心)
  16. LeetCode题解之Binary Tree Postorder Traversal
  17. 注册COM
  18. 复习,关于server.xml的一点理解
  19. 【ASP.NET MVC系列】浅谈MVC
  20. 使用泛型与不使用泛型的Map的遍历

热门文章

  1. 【Tomcat】使用tomcat manager 管理和部署项目,本地部署项目到服务器
  2. (6)DataTable 转换成 Json
  3. ubuntu下安装翻译软件
  4. Nginx配置文件语法教程
  5. Go -- 中结构体与字节数组能相互转化
  6. Angularjs: call other scope which in iframe
  7. linux 源码编译安装apache
  8. HDU 1003 Max Sum (动规)
  9. palindrome-partitioning I&amp;II——回文切割、深度遍历
  10. android项目笔记(一)