轉(zhuǎn)轉(zhuǎn)：   
 http://hi.baidu.com/ecchi/blog/item/84bcdc3ff832a5c37d1e71bf.html
  Trie樹2007-03-12 17:46轉(zhuǎn)自xiaoyao4005.cublog.cnTrie樹既可用于一般的字典搜索，也可用于索引查找。對于給定的一個字符串a(chǎn)1,a2,a3,...,an.則采用TRIE樹搜索經(jīng)過n次搜索即可完成一次查找。不過好像還是沒有B樹的搜索效率高，B樹搜索算法復雜度為logt(n+1/2).當t趨向大，搜索效率變得高效。怪不得DB2的訪問內(nèi)存設置為虛擬內(nèi)存的一個PAGE大小，而且?guī)袚Q頻率降低，無需經(jīng)常的PAGE切換。// trie.cpp : 定義控制臺應用程序的入口點。

http://acm.pku.edu.cn/JudgeOnline/problem?id=2564

//trie樹加動態(tài)規(guī)劃
//剛開始以為會超時,以為復雜度是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;
}