poj1204之AC自动机
Time Limit: 5000MS | Memory Limit: 65536K | |||
Total Submissions: 8235 | Accepted: 3104 | Special Judge |
Description
Even though word puzzles may be entertaining to solve by hand, they may become boring when they get very large. Computers do not yet get bored in solving tasks, therefore we thought you could devise a program to speedup (hopefully!) solution finding in such puzzles.
The following figure illustrates the PizzaHut puzzle. The names of the pizzas to be found in the puzzle are: MARGARITA, ALEMA, BARBECUE, TROPICAL, SUPREMA, LOUISIANA, CHEESEHAM, EUROPA, HAVAIANA, CAMPONESA.
Your task is to produce a program that given the word puzzle and words to be found in the puzzle, determines, for each word, the position of the first letter and its orientation in the puzzle.
You can assume that the left upper corner of the puzzle is the origin, (0,0). Furthemore, the orientation of the word is marked clockwise starting with letter A for north (note: there are 8 possible directions in total).
Input
Output
Sample Input
20 20 10
QWSPILAATIRAGRAMYKEI
AGTRCLQAXLPOIJLFVBUQ
TQTKAZXVMRWALEMAPKCW
LIEACNKAZXKPOTPIZCEO
FGKLSTCBTROPICALBLBC
JEWHJEEWSMLPOEKORORA
LUPQWRNJOAAGJKMUSJAE
KRQEIOLOAOQPRTVILCBZ
QOPUCAJSPPOUTMTSLPSF
LPOUYTRFGMMLKIUISXSW
WAHCPOIYTGAKLMNAHBVA
EIAKHPLBGSMCLOGNGJML
LDTIKENVCSWQAZUAOEAL
HOPLPGEJKMNUTIIORMNC
LOIUFTGSQACAXMOPBEIO
QOASDHOPEPNBUYUYOBXB
IONIAELOJHSWASMOUTRK
HPOIYTJPLNAQWDRIBITG
LPOINUYMRTEMPTMLMNBO
PAFCOPLHAVAIANALBPFS
MARGARITA
ALEMA
BARBECUE
TROPICAL
SUPREMA
LOUISIANA
CHEESEHAM
EUROPA
HAVAIANA
CAMPONESA
Sample Output
0 15 G
2 11 C
7 18 A
4 8 C
16 13 B
4 15 E
10 3 D
5 1 E
19 7 C
11 11 H
题意:输入n,m,w代表先给定n行m列字符,接下来w行每行给定一组字符串,求该字符串在n*m的矩阵中首先出现的起始位置,字符串可以和矩阵中以某点开始8个方向进行匹配
输出首先匹配的起始点坐标和匹配的方向
方向为A,B,C,D...
分析:将w各字符串插入字典树,然后用n*m的矩阵去匹配,匹配方法是枚举8个方向去匹配
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
#include<map>
#include<iomanip>
#define INF 99999999
using namespace std; const int MAX=1000+10;
char s[MAX][MAX],b[MAX];
int n,m,w;
int dir[8][2]={0,1,0,-1,1,0,-1,0,1,1,-1,-1,1,-1,-1,1};//八个方向
char ch[9]="CGEADHFB";
int pos[MAX][3]; struct TrieNode{
int id;//记录第几个字符串
TrieNode *next[26],*fail;
TrieNode(){
id=0;
fail=0;
memset(next,0,sizeof next);
}
}*root; void InsertNode(char *a,int id){
int len=strlen(a)-1;
TrieNode *p=root;
while(len>=0){//这里将a数组倒着插入字典树,方便匹配时记录匹配的终点即原串的起始点
if(!p->next[a[len]-'A'])p->next[a[len]-'A']=new TrieNode;
p=p->next[a[len--]-'A'];
}
p->id=id;
} void Build_AC(){
TrieNode *p=root,*next;
queue<TrieNode *>q;
q.push(root);
while(!q.empty()){
p=q.front();
q.pop();
for(int i=0;i<26;++i){
if(p->next[i]){
next=p->fail;
while(next && !next->next[i])next=next->fail;
if(next)p->next[i]->fail=next->next[i];
else p->next[i]->fail=root;
q.push(p->next[i]);
}
}
}
} void SearchTrie(int x,int y,int d,int id){
TrieNode *p=root,*next;
while(x>=0 && y>=0 && x<n && y<m){
while(p && !p->next[s[x][y]-'A'])p=p->fail;
if(!p)p=root;
else p=p->next[s[x][y]-'A'];
next=p;
while(next != root){
if(next->id){//记录原串被匹配的起始点
int k=next->id;
if(pos[k][0]>x || (pos[k][0] == x && pos[k][1]>y)){
pos[k][0]=x,pos[k][1]=y,pos[k][2]=id;
}
}
next=next->fail;
}
x+=dir[d][0];
y+=dir[d][1];
}
} void Free(TrieNode *p){
for(int i=0;i<26;++i)if(p->next[i])Free(p->next[i]);
delete p;
} int main(){
while(cin>>n>>m>>w){
root=new TrieNode;
for(int i=0;i<n;++i)cin>>s[i];
for(int i=1;i<=w;++i){
cin>>b;
InsertNode(b,i);
pos[i][0]=pos[i][1]=INF;
}
Build_AC();
for(int i=0;i<n;++i){
SearchTrie(i,0,0,1),SearchTrie(i,m-1,1,0);//匹配左右方向
SearchTrie(i,0,7,6),SearchTrie(i,m-1,6,7);//匹配左上部分的右上角和右下部分左下角
SearchTrie(i,0,4,5),SearchTrie(i,m-1,5,4);//匹配左下部分右下角和右上部分左上角
}
for(int i=0;i<m;++i){
SearchTrie(0,i,2,3),SearchTrie(n-1,i,3,2);//匹配上下方向
SearchTrie(0,i,6,7),SearchTrie(n-1,i,7,6);//匹配左上部分左下角和右下部分右上角
SearchTrie(0,i,4,5),SearchTrie(n-1,i,5,4);//匹配右上部分的右下角和左下部分左上角
}
for(int i=1;i<=w;++i)cout<<pos[i][0]<<' '<<pos[i][1]<<' '<<ch[pos[i][2]]<<endl;
Free(root);
}
return 0;
}
最新文章
- infopath重复表格无法保存输入内容
- 为什么C语言中的数组序号都是从0开始
- redis 在linux下的安装
- Android中对Log日志文件的分析[转]
- Communication System(dp)
- Java 数据类型转换
- 【原】Storm基本概念
- Java学习随笔——RMI
- (C#)Windows Shell 外壳编程系列6 - 执行
- Java socket通信
- pytest 13 使用自定义标记mark
- react_app 项目开发 (8)_角色管理_用户管理----权限管理 ---- shouldComponentUpdate
- Lecture6.概率极限理论
- Springboot 学习教程(一):版本+ jdk 版本 + Maven 版本的匹配
- 因 URL 意外地以“/HelloWorld”结束,请求格式无法识别。
- [转]HEX文件格式解析
- 在Docker中安装配置Oracle12c并实现数据持久化
- datasnap服务器支持的参数类型
- 【Coursera】Sixth Week(1)
- net start mysql启动mysql,提示发生系统错误 5 拒绝访问 解决方法
热门文章
- html5 本地存储
- webkit的基本应用
- -_-#【Backbone】Collection
- 附加数据库 对于 服务器“00-PC”失败
- http 400 错误的请求怎么解决
- 转自http://blog.sina.com.cn/daylive——C++ STL map
- 大暴力——[HAOI]2012音量调节
- JSP学习笔记(三):简单的Tomcat Web服务器
- 最长回文子串(百度笔试题和hdu 3068)
- POJ1505:Copying Books(区间DP)