实现了下Backward Nondeterministic Dawg Matching algorithm

yjm0573

1. 
   
2. /*
   
3. * A class for string matching use the
   
4. *  Backward Nondeterministic Dawg Matching algorithm
   
5. *
   
6. *  2008/2/26
   
7. *
   
8. *  By Yao Jianming
   
9. */
   
10. 
    
11. #ifndef _BNDMMATCH_H
    
12. #define _BNDMMATCH_H
    
13. 
    
14. #ifndef STRMATCH_MAXCHER
    
15. #define STRMATCH_MAXCHER 256
    
16. #endif
    
17. 
    
18. #include <string>
    
19. 
    
20. class strmatch {
    
21. private:
    
22.     std::string str;
    
23.     int mask[STRMATCH_MAXCHER];
    
24. 
    
25.     void makemasktable();
    
26. 
    
27. public:
    
28.     strmatch(const char* p) : str(p) {makemasktable();}
    
29. 
    
30.     void* search(const void* haystack, size_t haystack_len) const;
    
31. };
    
32. 
    
33. #endif
    
34. 
    
35. 
    
36. #include "strmatch.h"
    
37. 
    
38. void strmatch::makemasktable()
    
39. {
    
40.     memset(mask, 0, STRMATCH_MAXCHER*sizeof(int));
    
41. 
    
42.     const char* patt = str.c_str();
    
43.     int len = str.size();
    
44. 
    
45.     int s =1;
    
46.     for(int i = len - 1; i >= 0; --i) {
    
47.         mask[patt[i]] |= s;
    
48.         s <<= 1;
    
49.     }
    
50. }
    
51. 
    
52. void* strmatch::search(const void* haystack, size_t haystack_len) const
    
53. {
    
54.     const char* text = (const char*)haystack;
    
55.     const char* patt = str.c_str();
    
56.     int len = str.size();
    
57.     int k = 0;
    
58. 
    
59.     while(k <= haystack_len - len) {
    
60.         int i, d = ~0, shift = len;
    
61.         for(i = len - 1; i >= 0 && d != 0; --i) {
    
62.             d &= mask[text[k+i]];
    
63.             d <<= 1;
    
64.         }
    
65. 
    
66.         if(i < 0 && d != 0)
    
67.             return (void*)(text + k + i + 1);
    
68. 
    
69.         if(text[k+i+2] == patt[0])
    
70.             shift = i + 2;
    
71.             
    
72.         k += shift;
    
73.     }
    
74.    
    
75.     return (void*)NULL;
    
76. }
    
77. 
    
78. 
    
79. #include <sys/time.h>
    
80. #include "strmatch.h"
    
81. 
    
82. main()
    
83. {
    
84.     struct timeval start, end;
    
85.     gettimeofday(&start, 0);
    
86. 
    
87.     strmatch str = "helloworld";
    
88.     char text[] = "aaaadfjdfddfdkfalhelloworld";
    
89.     char* p = (char*)str.search(text, strlen(text));
    
90.     if(p != NULL) printf("%s\n", p);
    
91. 
    
92.     gettimeofday(&end, 0);
    
93.     long ltime = (end.tv_sec - start.tv_sec) * 1000000 +
    
94.                     end.tv_usec - start.tv_usec;
    
95.     printf("ltime: %ld\n", ltime);
    
96. }

复制代码

试过了能用，各位给看看，哪里需要改进

[ 本帖最后由 yjm0573 于 2008-2-29 10:10 编辑 ]

yjm0573

后面的怎么变那种字体了？.....................修改过来了

[ 本帖最后由 yjm0573 于 2008-2-26 12:09 编辑 ]