[导入]最长前缀匹配法 统计不同单词个数

如果使用概率算法的话,虽然速度较快,但会有一定的误差,而且这种误差还不稳定。
考虑使用确定算法,一般来讲,单词数量越多,第n个需要进行比较的单词操作时间越长。
今天在bbs上看到一种字典序的方法,每个单词与已经存在的单词的比较的时间花费只和自身的长度有关。也就是这样做得:
单词中的第i(0<i<n+1)位字母有26(对应26个英文字母)个预置位置,其(ASII-'a')值为其占有的位置,每个位置设置1个标志位标识该位是否是单词结束字母位置,定义每个对象都包含26个预留位置、1个标志符和指向下一个对象的指针。每个单词只需要按照顺序寻找第i位字母的对应位置,如果位置被占,直接寻找第i+1个字母的位置,如没有被占,就把这个位置new出来,直到最后一个字母,然后查看最后一位字母的位置的标识,如是被修改过,则是重复出现的单词,否则是新单词。  叙述的很乱,还是直接上代码吧。

@感谢LevinLin同学的贡献

----------------------------------------------------
 1 #include<iostream> 
 2 using namespace std; 
 3 
 4 const int kind=26
 5 int same=0
 6 
 7 struct Treenode 
 8 
 9 bool wordend;    //标识位,是否是最后一个字母
10 Treenode* next[kind];   //第i+1个字母的的位置
11 Treenode() 
12 
13 wordend=false
14 for(int i=0;i<kind;i++
15 next[i]=NULL; 
16 
17 }; 
18 
19 void insert(Treenode* root,char *word) 
20 
21 Treenode* location=root; 
22 int i=0,branch=0
23 
24 while(word[i]!='\0'
25 
26 branch=word[i]-'a'
27 if(!(location->next[branch]))     //判断第i位是否已经被占
28 
29 location->next[branch]=new Treenode(); 
30 
31 i++
32 location=location->next[branch]; 
33 
34 if (location->wordend==false
35 
36 location->wordend=true;   //修改标识
37 
38 else 
39 same++;  //标识被修改过,是重复出现的单词
40 
41 
42 int main() 
43 
44 int n,i; 
45 char word[11]; 
46 Treenode *root=NULL; 
47 root=new Treenode(); 
48 cin>>n; 
49 for (i=0;i<n;i++
50 
51 cin>>word; 
52 insert(root,word); 
53 
54 cout<<n-same; 
55 return 0
56 }
类别:算法 查看评论
文章来源:http://hi.baidu.com/janqii/blog/item/ec5ba7bcbf08b90619d81ff8.html

posted on 2010-04-27 23:48 janqii 阅读(515) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


导航

统计

常用链接

留言簿

随笔档案(15)

搜索

最新评论

阅读排行榜

评论排行榜