10万个字符串,检查相同的.怎么找?

rock_jq

搞到数据库中去 呵呵

p4apple

字符串可以提前处理吗 ，如果字符串很少变化， 可以对字符串进行MD5编码， 的到MD5 列表， 然后对MD5列表排序， 得到MD5编码索引， 需要进行字符串查找时 ， 先找具有相同MD5的字符串， 然后仔细比较， 速度应该很快的的 。
如过数据时变动很大的， MD5索引可以用，hash ＋ 链表的方式 。 自持动态加载。

JohnBull

构建一个索引树！
讲课时用过这个例子，参考一下吧！

1. 
   
2. #define TREEWIDTH 256
   
3. 
   
4. typedef struct node_t {
   
5.         struct node_t *next[TREEWIDTH];
   
6.         int count;
   
7. } node_t;
   
8. 
   
9. /* 这个函数把一个word导入一个索引树，然后返回这个word以前曾经导入过多少次 */
   
10. int
    
11. indexword(node_t *head, const char *word)
    
12. {
    
13.         int i;
    
14.         node_t *cur,*new;
    
15. 
    
16.         for (i=0,cur=head;;++i) {
    
17.                 if (word[i]=='\0') {
    
18.                         cur->count=cur->count+1;
    
19.                         if (cur->count > 1) {
    
20.                                 return cur->count-1;
    
21.                         }
    
22.                         break;
    
23.                 }
    
24.                 if (cur->next[word[i]] == NULL) {
    
25.                         cur->next[word[i]] = (node_t*)malloc(sizeof(node_t));
    
26.                         if (cur->next[word[i]] == NULL) {
    
27.                                 return -1;
    
28.                         }
    
29.                 }
    
30.                 cur=cur->next[word[i]];
    
31.         }
    
32. 
    
33.         return 0;
    
34. }
    
35. 
    

复制代码

langue

btree?

BenBear

可以直接将所有字符串排序，然后二分查找，这个也不慢的。

要算 hash 的话，也不需要 md5 那么复杂的，毕竟 md5 太长了，比较不方便。我习惯这样算 hash:

1. 
   
2. int hash_str(const char* str)
   
3. {
   
4.   int h = 0;
   
5.   while (*str)
   
6.     h = h * 5 + *str++;
   
7.   return h;
   
8. }
   

复制代码

也可以对字符串的 pair<hash, index> 按 hash 排序，先对 hash 进行二分查找，再比较实际值。

liuty2006

原帖由 BenBear 于 2006-9-24 12:25 发表
可以直接将所有字符串排序，然后二分查找，这个也不慢的。

要算 hash 的话，也不需要 md5 那么复杂的，毕竟 md5 太长了，比较不方便。我习惯这样算 hash:
[CODE]
int hash_str(const char* str)
{
  int h ...

md5 什么意思?

flw

原帖由 liuty2006 于 2006-9-25 05:51 发表

md5 什么意思?

google md5

liuty2006

原帖由 flw 于 2006-9-25 09:29 发表

google md5

"MD5的全称是Message-Digest Algorithm 5（信息-摘要算法）" --- 好像用于加密,但与此查找相同字符串算法有什么关系?

unix_os

原帖由 liuty2006 于 2006-9-25 10:40 发表



"MD5的全称是Message-Digest Algorithm 5（信息-摘要算法）" --- 好像用于加密,但与此查找相同字符串算法有什么关系?

8懂这个木有关系。。。

有排序树。。。

unix_os

原帖由 BenBear 于 2006-9-24 12:25 发表
可以直接将所有字符串排序，然后二分查找，这个也不慢的。

要算 hash 的话，也不需要 md5 那么复杂的，毕竟 md5 太长了，比较不方便。我习惯这样算 hash:
[CODE]
int hash_str(const char* str)
{
  int h ...

排序二分法么。。。

老师提问就问这个D。。。。。:em11:

结果木有人回答上。。。:em11: