Chinaunix

标题: 分享一个C库函数：字符串范性匹配 [打印本页]
作者: cobras    时间: 2014-07-25 09:40
标题: 分享一个C库函数：字符串范性匹配
本帖最后由 cobras 于 2014-07-25 11:13 编辑

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

  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. */

  15. #include <string.h>

  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. }

  27. int nstr_pbrk(const char *s, int off, int lmt, const char *chr_list)
  28. {
  29.         int len;

  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. }

  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. }

  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;

  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. }

  120. int str_match(const char *text, const char *match)
  121. {
  122.         int text_len, match_len;

  124.         text_len = strlen(text);
  125.         match_len = strlen(match);
  126.         return nstr_match(text, text_len, match, match_len);
  127. }

  129. /* TESTCASE */

  131. #include <stdio.h>

  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. }

  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    时间: 2014-07-25 10:09
TEST: does string "abc.txt" match "*.txt?" ? YES
TEST: does string "abc.tt" match "*.t?t" ? NO
作者: cobras    时间: 2014-07-25 10:10
对于?和*的用法区别不太明了。需要进一步确定
作者: cobras    时间: 2014-07-25 10:11
*可以匹配0-MAX个。?只能匹配1个吗？
作者: cobras    时间: 2014-07-25 10:12
hellioncu一下就测出了矛盾。佩服
作者: cobras    时间: 2014-07-25 10:23
发布了一个修正版，感谢hellioncu
作者: hellioncu    时间: 2014-07-25 10:36
cobras 发表于 2014-07-25 10:23
发布了一个修正版，感谢hellioncu


改得还挺快
作者: cobras    时间: 2014-07-25 10:41
既然公开了，就要对广大用户负责。
作者: cobras    时间: 2014-07-25 11:13
更新第3版。修正一个错误。
作者: yulihua49    时间: 2014-07-25 12:41
cobras 发表于 2014-07-25 09:40
分享一个我写的C库函数：字符串范性匹配。
可广范用于各种搜索代码中。

有正则表达式，regex，为什么还要自己弄？
作者: yulihua49    时间: 2014-07-25 12:44
yulihua49 发表于 2014-07-25 12:41
有正则表达式，regex，为什么还要自己弄？

请：
man regex

比你这个功能强的多的多。。。。。
速度，估计你也比不了。
作者: cobras    时间: 2014-07-25 13:04
用regex当然更好。不过License嘛。gpl的毒性扩散。。。
作者: cobras    时间: 2014-07-25 13:20
我知道正则表达式的强大，但我不需要那么多的功能。



欢迎光临 Chinaunix (http://bbs.chinaunix.net/) Powered by Discuz! X3.2