题意：给定一个n*m的字符阵列中，查找给出字串匹配的开始坐标位置， 配置可以是从开始坐标向四周8个方向。
分析：对需要匹配的字串建立trie树，枚举字符阵列的每个位置，每个方向，进行查询。
#include <iostream>
using namespace std;
const int MAX = 90000;
const int M = 26, N = 1005, W=1005;
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[] = {'A','B','C','D','E','F','G','H'};
int sx,sy;
int n,m,w;
int index;
char puzzles[N][N], word[W];
int r[W][3];
struct Node{
int end;
struct Node* child[M];
Node(){
end=-1;
memset(child,NULL,sizeof(child));
}
};
Node tree;
Node *root = &tree;
void insert( char* s, int d){
Node *node = root;
while(*s){
if(index==20){
printf(" ");
}
if(node->child[*s-'A']==NULL){
node->child[*s-'A'] = new Node;
}
node=node->child[*s-'A'];
s++;
}
node->end = d;
}
void search(int x, int y, int d){
Node *node = root->child[puzzles[x][y]-'A'];
if(node==NULL)
return;
while(node){
if(node->end>-1){
r[node->end][0] = sx;
r[node->end][1] = sy;
r[node->end][2] = d;
}
x=x+DX[d];
y=y+DY[d];
if( x>=0 && x<n && y>=0 && y<m ){
node=node->child[puzzles[x][y]-'A'];
}else
break ;
}
return;
}
void solve(){
int i,j,k;
for(i=0;i<n;++i)
for(j=0;j<m;++j)
for(k=0;k<8;++k){
sx = i;
sy = j;
search(i,j,k);
}
}
int main(){
int i;
scanf("%d%d%d", &n, &m, &w);
for(i=0;i<n;++i){
scanf("%s", &puzzles[i]);
}
for(i=0;i<w;++i){
scanf("%s", &word[i]);
insert(&word[i],i);
}
solve();
for(i=0;i<w;++i)
printf("%d %d %c\n", r[i][0], r[i][1], D[r[i][2]]);
return 0;
}posted on 2011-03-16 00:41
小阮 阅读(243)
评论(0) 编辑 收藏 引用 所属分类:
数据结构和算法 、
POJ