写的第一道 AC自动机 的题目
题目地址
思路参考：http://blog.csdn.net/jyysc2010/article/details/10429715
不是很熟悉所以花了挺长时间
因为是求第一点的所在位置所以将字符倒序插入trie树中，这样直接就能求的起点，但方向正好与原来相反
同时对每一个字符串编号，这样就知道走到终止结点是什么字符串了
走到一个终止结点就要顺着前驱指针走，防止后缀子字符串被忽略
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int letter=26;
const int maxn=1000+5;
int R,C,nNode;
struct Node{Node* pChild[26];Node* pPrev;int idx; bool bBadNode;Node(){memset(pChild,0,sizeof(pChild));pPrev=NULL; idx=0; bBadNode=false;}
}tree[100000];
char patten[maxn][maxn];
char words[maxn];
int ansX[maxn],ansY[maxn],ansD[maxn];
void Insert(Node* root,char* s,int t)
{for(int i=0;s[i];i++){if(root->pChild[s[i]-'A']==NULL)root->pChild[s[i]-'A']=tree+nNode++;root=root->pChild[s[i]-'A'];}root->idx=t;root->bBadNode=true;
}
void BuildDfa()
{for(int i=0;i<letter;i++)tree[0].pChild[i]=tree+1;tree[1].pPrev=tree;tree[0].pPrev=NULL;queue<Node*> Q;Q.push(tree+1);while(!Q.empty()){Node* root=Q.front(); Q.pop();for(int i=0;i<letter;i++){Node* p=root->pChild[i];if(p==NULL) continue;Node* pPrev=root->pPrev;while(pPrev!=NULL){if(pPrev->pChild[i]!=NULL){p->pPrev=pPrev->pChild[i];if(p->pPrev->bBadNode) p->bBadNode=true;break; //只要找一次后缀节点就好了，因为建dfa是一层一层来的，上一层肯定已经好了 }else pPrev=pPrev->pPrev;}Q.push(p);}}
}
const int dx[]={-1,-1,0,1,1,1,0,-1};
const int dy[]={0,1,1,1,0,-1,-1,-1};
const char d[]="EFGHABCD";
bool inline inside(int x,int y){ return x>=0&&x<R&&y>=0&&y<C;
}
void SearchDfa(int i,int j,int k)
{Node* p=tree+1;for(int x=i,y=j;inside(x,y);x+=dx[k],y+=dy[k]){for(;;){if(p->pChild[patten[x][y]-'A']!=NULL){p=p->pChild[patten[x][y]-'A'];Node* pPrev=p;while(pPrev->bBadNode){ //顺着前驱指针走 if(pPrev->idx){ansX[pPrev->idx]=x;ansY[pPrev->idx]=y;ansD[pPrev->idx]=k;pPrev->idx=0;}pPrev=pPrev->pPrev;}break;}else p=p->pPrev;}}
}
int main()
{int N;cin>>R>>C>>N;for(int i=0;i<R;i++)scanf("%s",patten[i]);nNode=2;for(int i=0;i<N;i++){scanf("%s",words);reverse(words,words+strlen(words));Insert(tree+1,words,i+1);}BuildDfa();for(int i=0;i<R;i++) { SearchDfa(i,0,2); SearchDfa(i,C-1,6); SearchDfa(i,0,3); SearchDfa(i,C-1,7); SearchDfa(i,0,1); SearchDfa(i,C-1,5); } for(int j=0;j<C; j++) { SearchDfa(R-1,j,0); SearchDfa(0,j,4); SearchDfa(0,j,3); SearchDfa(R-1,j,7); SearchDfa(R-1,j,1); SearchDfa(0,j,5); } for(int i=1;i<=N;i++){ cout<<ansX[i]<<' '<<ansY[i]<<' '<<d[ansD[i]]<<endl; }return 0;
}