字符串前缀：字典树（Trie）的应用

问题：给定一个字符串类型的数组， 其中不含有重复的字符串， 如果其中某一个字符串是另一个 字符串的前缀， 返回 true； 如果没有任何一个字符串是另一个字符串的前缀， 返回 false。
1.设计：为了使用字典树，需要用链将各个节点连接在一起，想到使用链表，为了方便使用函数对节点进行处理，把函数封装到节点内，考虑使用结构体或类；
2.实现：
（1）将节点封装为结构体，相应的处理函数作为其成员函数，这样在使用递归扫描节点的时候可以使用节点的指针调用节点的函数，相当于一条链链接下来，方便递归处理；
（2）hash_map：存储节点之间的边，以及边上的字符；
（3）先递归建立字典树，再递归对其搜索；
3.实验：因为建树和搜索都是递归进行的，并且是按照字符顺序的，所以字符串中有没有相同字符都可以；
当然，既然是搜索前缀当然是前面的字符都要相同，所以不用封装直接扫字符串也是可以的。

#include <iostream>
#include <stdlib.h>
#include <string>
#include <hash_map>

using namespace std;

typedef struct _Trie Trie;
typedef struct _Trie* pTrie;

/************************************ 
// 函数名称: 字符串前缀hasPrefix 
// 作 成 者：Erick.Wang 
// 作成日期：2016/08/17 
// 返 回 值: bool 
// 参 数: string 
// 函数说明：字典树Trie的应用（单支树，链表）
//************************************/  

struct _Trie 
{ 
    hash_map<char,pTrie> hmap;
//查找前缀
bool prefixChk(string s,int i)
    {
if (i == s.length()){
return true;
        }
        hash_map<char,pTrie>::iterator it;
        it = hmap.find(s[i]);
if (it != hmap.end()){
return it->second->prefixChk(s,i+1);
        }else{
return false;
        }            
    }

//创建Trie
void createTrie(string s,int i)
    { 
if(i == s.length())
return;
        pTrie tmp = new Trie();
        hmap.insert(pair<char,pTrie>(s[i],tmp));
        hmap.find(s[i])->second->createTrie(s,i+1);      
    }

bool hasPrefix(string s,string t)
    {
if (s.length() == 0 || t.length() == 0 || s == "" || t == ""){
return false;
        }
if (s == t){
return true;
        }
//用长字符串建树，用短字符串来匹配
if (s.length() < t.length()){ 
            createTrie(t,0);
return prefixChk(s,0);
        }else{
            createTrie(s,0);
return prefixChk(t,0);
        }
    }
};

//既然是前缀，那么字符串前面的字母必须相同，只需依次遍历字符串
bool hasPrefix2(string s,string t)
{
int i=0,j=0;
while (i<s.length() && j<t.length()){
if (s[i] == t[j]){
            i++;
            j++;
        }else{
return false;
        }
    }
return true;
}

int main()
{
string s = "11223";
string t = "1123";
    Trie trie;
cout << trie.hasPrefix(s,t)<<endl;

cout << hasPrefix2(s,t)<<endl;

    system("pause");
return 0;
}