题目link:http://acm.hdu.edu.cn/showproblem.php?pid=1857
先简述一下题目：
有一个RXC的字母矩形，R,C在500内，要匹配m个单词，m在100000内，每个单词长度不超过20,匹配方法为向右或者向下，或者右下，即三个方向,0度，90度，45度。
现在要输出：如果匹配成功，输出第一个字母的坐标，如果有多个匹配，输出最左上的，如果不成功，输出-1 -1。
如果你使用简单的匹配，或者搜索，超时无限次，如果你字母矩阵构树单词构trie树，必超内存，自己可以想想。
所以我也很无奈，这是我比赛时候遇到的一题，当时我开了这题，很无力……
这题目标志着我开始学习trie树，经过两天的思考，和参阅别人的思想，我们用逆向思维来做，以需匹配的单词构树（只有100000个），用字母矩阵来匹配，所以在插入的时候，我们给要匹配的单词编号，用RR,CC数组来记录对应单词的坐标，初始化为0（我用的是0,也可以memset( ,-1, )），之后查找的时候，就传入(行数+1,列数+1,)之所以加1，是因为想用0来表示没成功匹配。我在trie里写了terminable，id(属于第几个单词插入)属性，在查找过程，只要遇到结点terminable,就比较是否记载过，没记载过，就将RR[id],CC[id]标记为传入参数r,c。最后顺序输出即可。
想清楚后，昨晚很自信地开始拍了，经过各种调试，总算过了sample了……马上就提交了，这次终于没有TLE了，且速度十分快……在c++提交是wa,在g++提交是RE。
这时候已经很夜了，我心想，先休息吧……
每次带着问题休息，效果都会很差，想了很久，还是觉得没问题，最后在郁闷与猜疑中睡去了.
今天醒来，发现了一个很基本的错误，我的数组开得太小了……改了一下，马上就过掉了……！！！！
#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(){
memset(child,,sizeof(child)); //初始化节点
} };
int RR[],CC[];
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=;i<Size;i++)
root.child[i]=;
}
//插入
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]==){ 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]==){ 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=;i<Size;i++){
if(cur.child[i]==)continue; //不存在
clear_node(*cur.child[i]);
delete cur.childe[i];
cur.child[i]=;
if(--cur.node==) break; //没有节点了 } } //根
node_type root;
//字符转索引，类似hash
Index index; }; class IndexClass{
public:
int operator[](const char key){
return key%; //一个映射 } };
char cc[][];
char s[];
int mini(int a,int b){
return a>b?b:a;
}
int main(){
trie<,IndexClass> t;
int R,C,i,j,l,ed;
scanf("%d%d",&R,&C);
getchar(); //读掉回车
for( i=;i<R;i++)
{ gets(cc[i]);
} int N=;
while(gets(s)&&s[]!='-'){
if(s[]){
t.insert(s,N); //用每一个要查找的单词构树
N++;
} } for(i=;i<R;i++)
for( j=;j<C;j++){
//向下
memset(s,,sizeof(s));
if(i+<R) ed=;
else ed=R-i;
for(l=;l<ed;l++){
s[l]=cc[i+l][j]; } t.find(s,i+,j+);
//向右
memset(s,,sizeof(s));
if(j+<C) ed=;
else ed=C-j;
for( l=;l<ed;l++){
s[l]=cc[i][j+l]; } t.find(s,i+,j+); //右下
memset(s,,sizeof(s));
if(i+<R&&j+<C) ed=;
else ed=mini(C-j,R-i);
for( l=;l<ed;l++){
s[l]=cc[i+l][j+l]; } t.find(s,i+,j+); } for( i=;i<N;i++){ if(RR[i]!=||CC[i]!=)
printf("%d %d\n",RR[i]-,CC[i]-);
else puts("-1 -1");
} return ; }