POJ1204：Word Puzzles——题解

http://poj.org/problem?id=1204

题目大意：给一个字母表，求一些字符串的开端第一次出现的位置和字符串的方向（字符串可以按照八个方向放在字母表中可匹配的位置）

————————————————————————————————

一定是AC自动机，而且我们不可能对二位字母表AC一下，所以我们要把待匹配串AC一下，然后枚举字母表的起点（不要枚举多了），ACcheck一下就好了，蛮裸的。

为了保证最小序，需要对枚举顺序改一下，具体循环方法我piao了这位大佬的博客。

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<queue>
using namespace std;
const int L=1001;
const int C=1001;
const int M=1501;
const int W=1001;
int dx[8]={0,1,0,-1,1,1,-1,-1};
int dy[8]={1,0,-1,0,-1,1,1,-1};
char dir[8]={'C','E','G','A','F','D','B','H'};
struct trie{
    int ed;
    int a[26];
    int fail;
    int l;
}tree[C*L]={0};
char mp[L][C],s[M];
int ans[W][3];
bool vis[W];
int cnt=0,l,c,w;
inline void insert(int k){
    int now=0;
    int len=strlen(s);
    for(int i=0;i<len;i++){
        int t=s[i]-'A';
        if(!tree[now].a[t]){
            cnt++;
            tree[now].a[t]=cnt;
        }
        now=tree[now].a[t];
    }
    tree[now].ed=k;
    tree[now].l=len;
    return;
}
int q[C*L];
void getfail(){
    int r=0;
    //以下是对第一层的特殊处理 
    for(int i=0;i<26;i++){
        if(tree[0].a[i]!=0){
            tree[tree[0].a[i]].fail=0;
        r++;q[r]=tree[0].a[i];
        }
    }
    for(int l=1;l<=r;l++){
        int u=q[l];
        for(int i=0;i<26;i++){
            if(tree[u].a[i]!=0){
                tree[tree[u].a[i]].fail=tree[tree[u].fail].a[i];
        r++;q[r]=tree[u].a[i];
            }else{
                tree[u].a[i]=tree[tree[u].fail].a[i];
            }
        }
    }
    return;
}
void check(int x,int y,int d){
    int now=0;
    while(x>=0&&x<l&&y>=0&&y<c){
        int t=mp[x][y]-'A';
        now=tree[now].a[t];
        for(int j=now;j;j=tree[j].fail){
        int k=tree[j].ed;
        int len=tree[j].l-1;
            if(k&&!vis[k]){
        vis[k]=1;
        ans[k][0]=x-dx[d]*len;
        ans[k][1]=y-dy[d]*len;
        ans[k][2]=d;
        }
        }
    x+=dx[d];
    y+=dy[d];
    }
    return;
}
int main(){
    cin>>l>>c>>w;
    for(int i=0;i<l;i++){
    cin>>mp[i];
    }
    for(int i=1;i<=w;i++){
    cin>>s;
    insert(i);
    }
    getfail();
    for(int i=0;i<l;i++)
    for(int j=0;j<8;j++)
        check(i,0,j);
    for(int i=0;i<l;i++)
    for(int j=0;j<8;j++)
        check(i,c-1,j);
    for(int i=0;i<c;i++)
    for(int j=0;j<8;j++)
        check(0,i,j);
    for(int i=0;i<c;i++)
    for(int j=0;j<8;j++)
        check(l-1,i,j);
    for(int i=1;i<=w;i++)
    printf("%d %d %c
",ans[i][0],ans[i][1],dir[ans[i][2]]);
    return 0;
}