分享一个C库函数：字符串范性匹配

cobras

分享一个我写的C库函数：字符串范性匹配。
可广范用于各种搜索代码中。

1. 
   
2. /*
   
3. * note:
   
4. *
   
5. * 1 '*' matches 0 - MAX characters
   
6. * 2 '?' matches only 1 character
   
7. *
   
8. * changes:
   
9. *
   
10. * 1 first
    
11. * 2 fix hellioncu@chinaunix bug (? need to match only one character)
    
12. * 3 fix bug (text length less than rules)
    
13. */
    
14. 
    
15. #include <string.h>
    
16. 
    
17. int nstr_chr(const char *s, int off, int lmt, int c)
    
18. {
    
19.         for (; off < lmt; ++off) {
    
20.                 if (s[off] == c) {
    
21.                         return off;
    
22.                 }
    
23.         }
    
24.         return -1;
    
25. }
    
26. 
    
27. int nstr_pbrk(const char *s, int off, int lmt, const char *chr_list)
    
28. {
    
29.         int len;
    
30. 
    
31.         len = strlen(chr_list);
    
32.         for (; off < lmt; ++off) {
    
33.                 if (nstr_chr(chr_list, 0, len, s[off]) != -1) {
    
34.                         return off;
    
35.                 }
    
36.         }
    
37.         return -1;
    
38. }
    
39. 
    
40. int nstr_nstr(const char *s, int off, int lmt, const char *text, int text_len)
    
41. {
    
42.         lmt -= text_len;
    
43.         for (; off <= lmt; ++off) {
    
44.                 if (strncmp(s + off, text, text_len) == 0) {
    
45.                         return off;
    
46.                 }
    
47.         }
    
48.         return -1;
    
49. }
    
50. 
    
51. int nstr_match(const char *text, int text_len, const char *rules, int rules_len)
    
52. {
    
53.         int i, j, k;
    
54.         int lmt;
    
55.         int next;
    
56.         int len;
    
57.         int c;
    
58. 
    
59.         i = 0;
    
60.         j = 0;
    
61.         while (i < rules_len) {
    
62.                 lmt = nstr_pbrk(rules, i, rules_len, "*?");
    
63.                 if (lmt == -1) {
    
64.                         lmt = rules_len;
    
65.                         next = lmt;
    
66.                         c = 0;
    
67.                 }else {
    
68.                         next = lmt + 1;
    
69.                         c = rules[lmt];
    
70.                 }
    
71.                 len = lmt - i;
    
72.                 if (len > 0) {
    
73.                         if (j + len > text_len) {
    
74.                                 return -1;
    
75.                         }
    
76.                         if (strncmp(text + j, rules + i, len) != 0) {
    
77.                                 return -1;
    
78.                         }
    
79.                 }
    
80.                 switch (c) {
    
81.                 case 0:
    
82.                         i = next;
    
83.                         j += len;
    
84.                         break;
    
85.                 case '?':
    
86.                         i = next;
    
87.                         j += len + 1;
    
88.                         if (j > text_len) {
    
89.                                 return -1;
    
90.                         }
    
91.                         break;
    
92.                 case '*':
    
93.                         i = next;
    
94.                         lmt = nstr_pbrk(rules, i, rules_len, "*?");
    
95.                         if (lmt == -1) {
    
96.                                 lmt = rules_len;
    
97.                         }
    
98.                         len = lmt - i;
    
99.                         while (j + len <= text_len) {
    
100.                                 k = nstr_nstr(text, j, text_len, rules + i, len);
     
101.                                 if (k == -1) {
     
102.                                         return -1;
     
103.                                 }
     
104.                                 j = k;
     
105.                                 if (nstr_match(text + j, text_len - j, rules + i, rules_len - i) == -1) {
     
106.                                         ++j;
     
107.                                         continue;
     
108.                                 }
     
109.                                 return 0;
     
110.                         }
     
111.                         return -1;
     
112.                 }
     
113.         }
     
114.         if (j < text_len) {
     
115.                 return -1;
     
116.         }
     
117.         return 0;
     
118. }
     
119. 
     
120. int str_match(const char *text, const char *match)
     
121. {
     
122.         int text_len, match_len;
     
123. 
     
124.         text_len = strlen(text);
     
125.         match_len = strlen(match);
     
126.         return nstr_match(text, text_len, match, match_len);
     
127. }
     
128. 
     
129. /* TESTCASE */
     
130. 
     
131. #include <stdio.h>
     
132. 
     
133. int test_str_match(const char *text, const char *match)
     
134. {
     
135.         printf("TEST: does string \"%s\" match \"%s\" ? ", text, match);
     
136.         if (str_match(text, match) == 0) {
     
137.                 printf("YES");
     
138.         }else {
     
139.                 printf("NO");
     
140.         }
     
141.         printf("\n");
     
142.         return 0;
     
143. }
     
144. 
     
145. int main(void)
     
146. {
     
147.         test_str_match("abc.txt", "*");
     
148.         test_str_match("abc.txt", "?");
     
149.         test_str_match("abc.txt", "abc.txt?"); /* add by hellioncu@chinaunix */
     
150.         test_str_match("abc.tt", "abc.t?t"); /* add by hellioncu@chinaunix */
     
151.         test_str_match("abc.txt", "abc.t?t");
     
152.         test_str_match("abc.txt", "abc.t?e");
     
153.         test_str_match("abc.txt", "*.txt");
     
154.         test_str_match("abc.txt", "*.txe");
     
155.         test_str_match("abc.txt", "*.txt*");
     
156.         test_str_match("abc.txt", "*.txe*");
     
157.         test_str_match("abc.txt.txe3", "*.t?t*");
     
158.         test_str_match("abc.txe.txt3", "*.t?t*");
     
159.         test_str_match("abc.txe.txe3", "*.t?t*");
     
160.         return 0;
     
161. }
     

复制代码

hellioncu

TEST: does string "abc.txt" match "*.txt?" ? YES
TEST: does string "abc.tt" match "*.t?t" ? NO

cobras

对于?和*的用法区别不太明了。需要进一步确定

cobras

*可以匹配0-MAX个。?只能匹配1个吗？

cobras

hellioncu一下就测出了矛盾。佩服

cobras

发布了一个修正版，感谢hellioncu

hellioncu

cobras 发表于 2014-07-25 10:23
发布了一个修正版，感谢hellioncu

改得还挺快

cobras

既然公开了，就要对广大用户负责。

cobras

更新第3版。修正一个错误。

yulihua49

cobras 发表于 2014-07-25 09:40
分享一个我写的C库函数：字符串范性匹配。
可广范用于各种搜索代码中。

有正则表达式，regex，为什么还要自己弄？