辞書ツリー(Trieツリー)の使い方と例(二)

うわつぎhttp://blog.csdn.net/u010902721/article/details/45749447
例2
質問:
AがBのプレフィックスであることを満たす2つの文字列AとBがあるかどうかの文字列のセットがあります.
分析:
私たちは「abcde」、「abcxy」、「ab」を区別すればいい.nodeでiはflagとして使用され、1はこの文字が挿入された文字列の末尾文字であることを示す.これで「ab」を先に挿入してから「abcde」を挿入すれば見つかります.また、「abcde」を先に挿入し、「ab」を挿入する可能性もあります.新しい文字列を挿入すると、文字列挿入が完了してもノードが新規に作成されていないことがわかり、trueも返されます.

#include<iostream>
#include<string>

using namespace std;
const int MAX_NUM = 26;
struct trieNode{
    int i;//   ， 1              
    struct trieNode *next[MAX_NUM];
};

trieNode* CreateTrieNode(){
    trieNode *p = new trieNode;
    p->i = 0;
    for(int i = 0; i < MAX_NUM; i++)
        p->next[i] = NULL;
    return p;
}

bool InsertTrieTree(trieNode **root, string str){
    trieNode *p;
    if(*root == NULL){
        p = CreateTrieNode();
        *root = p;
    }
    else
        p = *root;
    int len = str.length();
    int k;
    for(int i = 0; i < len; i++){
        k = str.at(i) - 'a';
        if(p->next[k] != NULL){
            if(p->next[k]->i == 1 || i+1 == len)//        
                return true;
        }
        else
            p->next[k] = CreateTrieNode();
        p = p->next[k];
    }
    p->i = 1;//     
    return false;
}

int main(){
    trieNode *root = NULL;
    cout << InsertTrieTree(&root, "checking");   //print 0
    cout << InsertTrieTree(&root, "check");      //print 1
    cout << InsertTrieTree(&root, "for");        //print 0
    cout << InsertTrieTree(&root, "checking");   //print 1
    cout << InsertTrieTree(&root, "program");    //print 0
    cout << InsertTrieTree(&root, "programmer"); //print 1
}