Trie,HDU1875world puzzle

附上代码

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<cmath>
#include<cstdlib>
using namespace std;
template<int Size>
struct trie_node{bool terminable; //表示节点为字符串的结尾
int node; //子节点的个数
int id;
trie_node *child[Size]; //儿子节点
trie_node():terminable(false), node(0){
memset(child,0,sizeof(child)); //初始化节点
}};
int RR[10200],CC[10200];
template<int Size,typename Index>
class trie{
public:
//定义类名
typedef trie_node<Size> node_type;
typedef trie_node<Size> *link_type;//构造函数
trie(Index i=Index()):index(i){ }//清空函数，用于析构
void clear(){
clear_node(root);
for(int i=0;i<Size;i++)
root.child[i]=0;
}
//插入
template<typename Iterator>
void insert(Iterator begin,Iterator end,int i){link_type cur= &root;//当前插入结点为根
while(begin!=end){
if(cur->child[index[*begin]]){//插入过
cur=cur->child[index[*begin]];
++(cur->node);}else{
cur->child[index[*begin]]=new node_type;
++(cur->child[index[*begin]]->node);
cur=cur->child[index[*begin]];}begin++; //迭代器往前走！
}
cur->terminable=true;
cur->id=i;}//重载c风格插入
void insert(const char * str,int i){
insert(str,str+strlen(str), i);
}//查找
template <typename Iterator>
void find(Iterator begin,Iterator end,int r,int c){
link_type cur=&root;
while(begin!=end){if(cur->terminable){if(RR[cur->id]==0){RR[cur->id]=r;
CC[cur->id]=c;
}
}if(!cur->child[index[*begin]]) //没有节点啊！！！
return ;cur=cur->child[index[*begin]];begin++;}
if( cur->terminable) {//是否为字符串if(RR[cur->id]==0){RR[cur->id]=r;
CC[cur->id]=c;
}
}}//重载c风格
void find(const char *str,int r,int c){find(str,str+strlen(str),r,c);
}private://清空
void clear_node(node_type cur){
for(int i=0;i<Size;i++){
if(cur.child[i]==0)continue; //不存在
clear_node(*cur.child[i]);
delete cur.childe[i];
cur.child[i]=0;
if(--cur.node==0) break; //没有节点了}}//根
node_type root;
//字符转索引，类似hash
Index index;};class IndexClass{
public:
int operator[](const char key){
return key%26; //一个映射}};
char cc[501][501];
char s[21];
int mini(int a,int b){
return a>b?b:a;
}
int main(){
trie<26,IndexClass> t;
int R,C,i,j,l,ed;
scanf("%d%d",&R,&C);
getchar(); //读掉回车
for( i=0;i<R;i++)
{gets(cc[i]);
}int N=0;
while(gets(s)&&s[0]!='-'){
if(s[0]){
t.insert(s,N);   //用每一个要查找的单词构树
N++;
}}for(i=0;i<R;i++)
for( j=0;j<C;j++){
//向下
memset(s,0,sizeof(s));
if(i+20<R) ed=20;
else ed=R-i;
for(l=0;l<ed;l++){
s[l]=cc[i+l][j];}t.find(s,i+1,j+1);
//向右
memset(s,0,sizeof(s));
if(j+20<C) ed=20;
else ed=C-j;
for( l=0;l<ed;l++){
s[l]=cc[i][j+l];}t.find(s,i+1,j+1);//右下
memset(s,0,sizeof(s));
if(i+20<R&&j+20<C) ed=20;
else ed=mini(C-j,R-i);
for( l=0;l<ed;l++){
s[l]=cc[i+l][j+l];}t.find(s,i+1,j+1);}for( i=0;i<N;i++){if(RR[i]!=0||CC[i]!=0)
printf("%d %d\n",RR[i]-1,CC[i]-1);
else puts("-1 -1");
}return 0;}