转转：
http://hi.baidu.com/ecchi/blog/item/84bcdc3ff832a5c37d1e71bf.html
Trie树2007-03-12 17:46转自xiaoyao4005.cublog.cnTrie树既可用于一般的字典搜索，也可用于索引查找。对于给定的一个字符串a1,a2,a3,...,an.则采用TRIE树搜索经过n次搜索即可完成一次查找。不过好像还是没有B树的搜索效率高，B树搜索算法复杂度为logt(n+1/2).当t趋向大，搜索效率变得高效。怪不得DB2的访问内存设置为虚拟内存的一个PAGE大小，而且帧切换频率降低，无需经常的PAGE切换。// trie.cpp : 定义控制台应用程序的入口点。
http://acm.pku.edu.cn/JudgeOnline/problem?id=2564
//trie树加动态规划
//刚开始以为会超时,以为复杂度是o(25000*16*26)*o(16)
//还没搞明白那trie树的查询时间到底是o(1)还是o(16)呢?
#include<stdio.h>
#include<iostream>
#include<memory.h>
#include<string.h>
using namespace std;
#define MAX 25001
#define M 26
int rec,rec2;
char q[M];
char p[M];
int ans;
class Trie{
public:
Trie();
~Trie();
int insert(char *key);
int search(char *key);
struct Trie_node{
char *p;
int num;
Trie_node *next[M];
Trie_node();
};
Trie_node *root;
};
Trie::Trie_node::Trie_node(){
p=NULL;
for(int i=0;i<M;i++){
next[i]=NULL;
}
}
Trie::Trie(){
root=NULL;
}
Trie::~Trie(){
}
int Trie::insert(char *key){//插入，插入成功后返回1
int char_node;
char *g=new char[strlen(key)+1];
strcpy(g,key);
if(root==NULL){
root=new Trie_node;
}
Trie_node *cur=root;
while(cur&&*key!=0){
if(*key>='a'&&*key<='z'){
char_node=*key-'a';
}
else if(*key>='A'&&*key<='Z'){
char_node=*key-'A';
}
else return 0;
if(cur->next[char_node]==NULL){
cur->next[char_node]=new Trie_node;
}
cur=cur->next[char_node];
key++;
}
cur->num=rec2;
cur->p=new char[strlen(g)+1];
strcpy(cur->p,g);
return 1;
}
int Trie:: search(char *key)//查找，找到后放于entry中，返回1
{
Trie_node *cur=root;
int char_node;
char k[M];
strcpy(k,key);
while(cur&&*key!=0){
if(*key>='a'&&*key<='z'){
char_node=*key-'a';
}
else {if(*key>='A'&&*key<='Z'){
char_node=*key-'A';
}
else {return 0;}
}
cur=cur->next[char_node];
key++;
}
if(cur!=NULL&&cur->p!=NULL){
if(rec<cur->num+1){rec=cur->num+1;}
return 1;
}
return 0;
}
Trie t;
int Least(){
int i,j,k,q_len;
char ch,sh;
q_len=strlen(q);
rec=1;
for(i=0;i<q_len;i++){
for(k=j=0;j<q_len-1;j++,k++){
if(k==i)k++;
p[j]=q[k];
}
p[j]='\0';
t.search(p);
}
if(ans<rec)ans=rec;
rec2=rec;
rec=1;
for(i=0;i<q_len;i++){
ch=q[i];
for(sh='a';sh<='z';sh++){
q[i]=sh;
t.search(q);
}
q[i]=ch;
}
if(ans<rec)ans=rec;
if(rec2<rec)rec2=rec;
rec=1;
for(i=0;i<q_len;i++){
for(j=0;j<i;j++){
p[j]=q[j];
}
for(j=q_len;j>i;j--){
p[j]=q[j-1];
}
p[q_len+1]='\0';
for(sh='a';sh<='z';sh++){
p[i]=sh;
t.search(p);
}
}
strcpy(p,q);
p[q_len+1]='\0';
for(sh='a';sh<='z';sh++){
p[q_len]=sh;
t.search(p);
}
if(ans<rec)ans=rec;
if(rec2<rec)rec2=rec;
t.insert(q);
return 0;
}
int main(){
int i,j,k,g,q_len;
ans=0;
while(scanf("%s",q)!=EOF){
Least();
}
printf("%d\n",ans);
return 0;
}