Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## Re:AC自动机跑了2000+ms，估计比朴素都慢了悲剧……

Posted by hnust_xiaochaoqun at 2017-09-12 15:18:24 on Problem 1204
In Reply To:AC自动机跑了2000+ms，估计比朴素都慢了悲剧…… Posted by:xuhaoran510 at 2011-03-05 16:27:27
```500多ms。。也是ac自动机。

/**

AC自动机好文章：http://www.cppblog.com/menjitianya/archive/2014/07/10/207604.html
*/

//#include<bits/stdc++.h>
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
#define P pair<int,int>
#define ms(x,y) memset(x,y,sizeof x)
#define LL long long
const int maxn = 1005;
const int mod = 1e9+7;
const int maxnode = maxn*maxn;
const int sigma_size = 26;
struct node
{
int x, y, dir;
}ans[maxn];
int dir[8][2] = {{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}};
char s[maxn][maxn];
int sn, sm;
struct AhoCorasickAutomata
{
int ch[maxnode][sigma_size];
int val[maxnode];
int sz;
int f[maxnode];
int last[maxnode];
void clear(){sz = 1; memset(ch[0],0,sizeof ch[0]); }
int idx(char c){return c-'A'; }

void insert(char *s,int x)
{
int u = 0, n = strlen(s);
for(int i = 0; i < n; i++){
int c = idx(s[i]);
if(!ch[u][c]){
memset(ch[sz], 0, sizeof ch[sz]);
val[sz] = 0;
ch[u][c] = sz++;
}
u = ch[u][c];
}
val[u] = x;
}

void find(int x,int y,int f){
int j = 0;
while(x>=0&&x<sn&&y>=0&&y<sm){
int c = idx(s[x][y]);
j = ch[j][c];
if(val[j]) print(j,x,y,f);
else if(last[j]) print(last[j],x,y,f);
x = x+dir[f][0];
y = y+dir[f][1];
}
}

void print(int j,int x,int y,int dir)
{
if(j){
//cnt[val[j]]++;
ans[val[j]].x = x, ans[val[j]].y = y;
ans[val[j]].dir = dir;
print(last[j],x,y,dir);
}
}

void getFail(){
queue<int> q;
f[0] = 0;
for(int c = 0; c < sigma_size; c++){
int u = ch[0][c];
if(u){f[u] = 0; q.push(u); last[u] = 0;}
}

while(!q.empty()){
int r = q.front(); q.pop();
for(int c = 0; c < sigma_size; c++){
int u = ch[r][c];
if(!u){
ch[r][c] = ch[f[r]][c]; continue;
}//if(!u) continue;
q.push(u);
int v = f[r];
while(v&&!ch[v][c]) v = f[v];
f[u] = ch[v][c];
last[u] = val[f[u]] ? f[u] : last[f[u]];
}
}
}

} ac ;
char t[maxn];
int main()
{
int w;
while(scanf("%d%d%d",&sn,&sm,&w)!=EOF)
{
for(int i = 0; i < sn; i++) scanf("%s",s[i]);
ac.clear();
for(int i = 1; i <= w; i++){
scanf("%s",t);
reverse(t,t+strlen(t));///逆向插入，这样当查询的时候，当前的x，y就是起点。而不用回溯获取找起点。
///同理，方向的最终结果也要反向再输出。
ac.insert(t,i);
}
ac.getFail();
for(int i = 0; i < sm; i++){
ac.find(0,i,4);///向下
ac.find(sn-1,i,0);///向上
ac.find(0,i,5);///向左下
ac.find(0,i,3);///向右下
ac.find(sn-1,i,1);///向右上
ac.find(sn-1,i,7);///向左上
}
for(int i = 0; i < sn; i++){
ac.find(i,0,2);///向右
ac.find(i,sm-1,6);///向左
ac.find(i,0,3);///右下
ac.find(i,0,1);///右上
ac.find(i,sm-1,5);///左下
ac.find(i,sm-1,7);///左上
}
for(int i = 1; i <= w; i++){
printf("%d %d %c\n",ans[i].x,ans[i].y,(ans[i].dir+4)%8+'A');
}
}
return 0;
}

/*
QWSPILAATIRAGRAMYKEI
AGTRCLQAXLPOIJLFVBUQ
TQTKAZXVMRWALEMAPKCW
LIEACNKAZXKPOTPIZCEO
FGKLSTCBTROPICALBLBC
JEWHJEEWSMLPOEKORORA
LUPQWRNJOAAGJKMUSJAE
KRQEIOLOAOQPRTVILCBZ
QOPUCAJSPPOUTMTSLPSF
LPOUYTRFGMMLKIUISXSW
WAHCPOIYTGAKLMNAHBVA
EIAKHPLBGSMCLOGNGJML
LDTIKENVCSWQAZUAOEAL
HOPLPGEJKMNUTIIORMNC
LOIUFTGSQACAXMOPBEIO
IONIAELOJHSWASMOUTRK
HPOIYTJPLNAQWDRIBITG
LPOINUYMRTEMPTMLMNBO
PAFCOPLHAVAIANALBPFS
MARGARITA
ALEMA
BARBECUE
TROPICAL
SUPREMA
LOUISIANA
CHEESEHAM
EUROPA
HAVAIANA
CAMPONESA
*/

```

Followed by: