poj1204:http://poj.org/problem?id=1204
题意：给你n*m的字符串矩阵，然后p个查询，每个查询会给出一个字符串，然后问你在矩阵中能否通过8个方向搜索到这个字符串，输出地点以及搜索的方向。
题解：这里的思想真的很好。离线，把要查询的字符串插入trie树中，然后在矩阵中暴力查询查询。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 1100000
using namespace std;
const char BASE='A';
char str[][];
int len,n,m,p,stx,sty;
int as1[],as2[],as3[];
int dir[][]={{-,},{-,},{,},{,},{,},{,-},{,-},{-,-}};
bool vis[maxn];
int head[maxn]; // head[i]为第i个结点的左儿子编号
int next[maxn]; // next[i]为第i个结点的右兄弟编号
int id[maxn];
char ch[maxn]; // ch[i]为第i个结点上的字符
int sz; // 结点总数
void init(){
sz = ;
memset(head,,sizeof(head));
memset(next,,sizeof(next));
}
void insert(const char *s,int to,int num) {
int u = , v;
for(int i =; i <to; i++) {
bool found = false;
for(v = head[u]; v != ; v = next[v])
if(ch[v] == s[i]) { // 找到了
found = true;
break;
}
if(!found) {
v = ++sz; // 新建结点
ch[v] = s[i];
next[v] = head[u];
head[u] = v; // 插入到链表的首部
head[v] = ;
}
u = v;
}
id[sz]=num;
}
void DFS(int u,int x,int y,int num){
if(!u||x<||x>=n||y<||y>=m)return;
int v=;
for(v=head[u]; v!= ; v = next[v])
if(ch[v] == str[x][y]) { // 找到了
break;
}
if(id[v]){
int tt=id[v];
as1[tt]=stx,as2[tt]=sty,as3[tt]=num;
id[v]=;
}
DFS(v,x+dir[num][],y+dir[num][],num);
}
char temp[];
int main(){
while(~scanf("%d%d%d",&n,&m,&p)){
for(int i=;i<n;i++){
scanf("%s",str[i]);
}
init();
memset(vis,,sizeof(vis));
memset(id,,sizeof(id));
for(int i=;i<=p;i++){
scanf("%s",temp);
vis[temp[]-BASE]=;
insert(temp,strlen(temp),i);
}
for(int i=;i<n;i++){
for(int j=;j<m;j++){
if(vis[str[i][j]-BASE]){
for(int k=;k<;k++){
stx=i,sty=j;
DFS(,i,j,k);
}
}
}
}
for(int i=;i<=p;i++){
printf("%d %d %c\n",as1[i],as2[i],as3[i]+'A');
}
}
}