字典系列算法题目

wilbur8415

统计出，以某个字符串为前缀的，单词数量。  (单词本身，也是自己的前缀)



（字典先由用户输入（无序输入)；然后再由用户输入一个字符串，要求系统输出所有以这个字符串为前缀的单词）


比如 ：
请输入字典： banana   bamboo bee  absolute  band adam bra  boost （回车)
请输入待查找字符串:     ba（回车）
结果是:                     3

cugb_cat

trie树。

cjaizss

原帖由 cugb_cat 于 2008-4-9 15:24 发表
trie树。

顶，那天忘了这个树的名字，还特意问了一下。

cugb_cat

原帖由 cjaizss 于 2008-4-9 15:46 发表

顶，那天忘了这个树的名字，还特意问了一下。

在水木上问的的？

wilbur8415

恩 好 trie树

继续  换个题

用户输入一堆无序数   要求找出所有的满足以下条件的数a(a可以被拆分为2个数b,c ，而且b,c也属于用户输入的这一堆数)

比如输入

a
ahat
hat
hatword
hziee
word

那么ahat hatword满足条件 需要被打印出来

(因为ahat可以被写为 a和hat...)

要求高效实现

wilbur8415

最后来一个 实际原理都是一样的..

就是看优化的如何了

给定一个字符串例如“appleuwebananasdf”，和一个词典库（里面有apple ，banana ……），将其分词。结果应该为 “apple uwe banana sdf ”。
注意考虑词典库的大小。

请给出实现代码，并描述其时间复杂度。

cugb_cat

原帖由 wilbur8415 于 2008-4-9 16:31 发表
最后来一个 实际原理都是一样的..

就是看优化的如何了

给定一个字符串例如“appleuwebananasdf”，和一个词典库（里面有apple ，banana ……），将其分词。结果应该为 “apple uwe banana sdf ”。
注意 ...

这个还是trie树，只要词典库是以trie树组织的就行。

yecheng_110

这段时间正好学C++ 加之以前了解了一下trie 写了一个程序 贴出来让大家批批

1. 
   
2. #include <iostream>
   
3. #include <queue>
   
4. 
   
5. using namespace std;
   
6. 
   
7. class trieNode{
   
8.     private:
   
9.         char key;
   
10.         int value;
    
11.         trieNode *next;
    
12.         trieNode *child;
    
13. 
    
14.     public:
    
15.         friend class trie;
    
16.         trieNode():key('\0'),value(-1),next(NULL),child(NULL){}
    
17.         trieNode(char key,int value,trieNode *next,trieNode *child);
    
18.         void setValue(int value){this->value = value;}
    
19. };
    
20. 
    
21. trieNode::trieNode(char key,int value,trieNode *next,trieNode *child){
    
22.     this->key = key;
    
23.     this->value = value;
    
24.     this->next = next;
    
25.     this->child = child;
    
26. }
    
27. 
    
28. class trie{
    
29.     private:
    
30.         trieNode head;
    
31.     public:
    
32.         trie():head('\0',-1,NULL,NULL){}
    
33.         void addItem(const char *str,int value);
    
34.         void printTrie();
    
35.         void printNode(trieNode *first);
    
36.         int findPre(const char *str);
    
37. };
    
38. 
    
39. void trie::addItem(const char *str,int value){
    
40.     const char *p;
    
41.     trieNode *root;
    
42.     trieNode *t;
    
43.     trieNode *pre;
    
44.     trieNode *node;
    
45. 
    
46.     if(str == NULL){
    
47.         return ;
    
48.     }
    
49.     root = &head;
    
50.    
    
51.     for(p = str;;p++){
    
52.         pre = NULL;
    
53.         for(t = root->child;t != NULL;t = t->next){
    
54.             if(t->key == *p){
    
55.                 break;
    
56.             }
    
57.             pre = t;
    
58.         }
    
59.         if(t == NULL){
    
60.             node = new trieNode(*p,-1,NULL,NULL);   
    
61.             if(node == NULL){
    
62.                 return ;
    
63.             }
    
64.             if(pre == NULL){
    
65.                 root->child = node;
    
66.             }
    
67.             else{
    
68.                 pre->next = node;
    
69.             }
    
70.             root = node;
    
71.         }
    
72.         else{
    
73.             root = t;
    
74.         }
    
75.         if(*p == '\0'){
    
76.             node->setValue(value);
    
77.             break;
    
78.         }
    
79.     }
    
80. }
    
81. 
    
82. void trie::printTrie(){
    
83.     queue<trieNode *> triequ[2];
    
84.     trieNode *p;
    
85.     trieNode *root;
    
86.     int i = 0;
    
87.    
    
88.     triequ[i].push(&head);
    
89.     while(!triequ[i].empty()){
    
90.         while(!triequ[i].empty()){
    
91.             root = triequ[i].front();
    
92.             triequ[i].pop();
    
93.             if(root == NULL){
    
94.                 cout << endl;
    
95.                 continue;
    
96.             }
    
97.             for(p = root->child;p != NULL;p = p->next){
    
98.                 triequ[1 - i].push(p);
    
99.                 cout << p->key << "(" << p->value << "," << root->key << ")\t";
    
100.             }
     
101.         }
     
102.         cout << endl;
     
103.         i = 1 - i;
     
104.     }
     
105. }
     
106. 
     
107. int trie::findPre(const char *str){
     
108.     int count = 0;
     
109.     const char *p;
     
110.     trieNode *root;
     
111.     trieNode *t = NULL;
     
112.     queue<trieNode *> triequ;
     
113.    
     
114.     if(str == NULL || *str == '\0'){
     
115.         return count;
     
116.     }
     
117.     root = &head;
     
118.    
     
119.     for(p = str;*p != '\0';p++){
     
120.         for(t = root->child;t != NULL;t = t->next){
     
121.             if(t->key == *p){
     
122.                 break;
     
123.             }
     
124.         }
     
125.         if(t == NULL){
     
126.             return count;
     
127.         }
     
128.         root = t;
     
129.     }
     
130.     triequ.push(t);
     
131.     while(!triequ.empty()){
     
132.         root = triequ.front();
     
133.         triequ.pop();
     
134.         for(t = root->child;t != NULL;t = t->next){
     
135.             triequ.push(t);
     
136.             if(t->key == '\0'){
     
137.                 count++;
     
138.             }
     
139.         }
     
140.     }
     
141.    
     
142.     return count;
     
143. }
     
144. 
     
145. int main(){
     
146.     trie t;
     
147.     t.addItem("banana",1);
     
148.     t.addItem("bamboo",2);
     
149.     t.addItem("bee",3);
     
150.     t.addItem("absolute",4);
     
151.     t.addItem("bane",5);
     
152.     t.addItem("adam",6);
     
153.     t.addItem("bra",7);
     
154.     t.addItem("boost",8);
     
155. 
     
156.     t.printTrie();
     
157. 
     
158.     cout << t.findPre("bo") << endl;
     
159.         
     
160.     return 0;
     
161. }
     

复制代码

[ 本帖最后由 yecheng_110 于 2008-4-10 09:57 编辑 ]

tyz

继续 学习