免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
12下一页
最近访问板块 发新帖
查看: 3674 | 回复: 12

[C] 分享一个C库函数:字符串范性匹配 [复制链接]

论坛徽章:
2
2015年辞旧岁徽章
日期:2015-03-03 16:54:152015年迎新春徽章
日期:2015-03-04 09:56:11
发表于 2014-07-25 09:40 |显示全部楼层
本帖最后由 cobras 于 2014-07-25 11:13 编辑

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

  1. /*
  2. * note:
  3. *
  4. * 1 '*' matches 0 - MAX characters
  5. * 2 '?' matches only 1 character
  6. *
  7. * changes:
  8. *
  9. * 1 first
  10. * 2 fix hellioncu@chinaunix bug (? need to match only one character)
  11. * 3 fix bug (text length less than rules)
  12. */

  13. #include <string.h>

  14. int nstr_chr(const char *s, int off, int lmt, int c)
  15. {
  16.         for (; off < lmt; ++off) {
  17.                 if (s[off] == c) {
  18.                         return off;
  19.                 }
  20.         }
  21.         return -1;
  22. }

  23. int nstr_pbrk(const char *s, int off, int lmt, const char *chr_list)
  24. {
  25.         int len;

  26.         len = strlen(chr_list);
  27.         for (; off < lmt; ++off) {
  28.                 if (nstr_chr(chr_list, 0, len, s[off]) != -1) {
  29.                         return off;
  30.                 }
  31.         }
  32.         return -1;
  33. }

  34. int nstr_nstr(const char *s, int off, int lmt, const char *text, int text_len)
  35. {
  36.         lmt -= text_len;
  37.         for (; off <= lmt; ++off) {
  38.                 if (strncmp(s + off, text, text_len) == 0) {
  39.                         return off;
  40.                 }
  41.         }
  42.         return -1;
  43. }

  44. int nstr_match(const char *text, int text_len, const char *rules, int rules_len)
  45. {
  46.         int i, j, k;
  47.         int lmt;
  48.         int next;
  49.         int len;
  50.         int c;

  51.         i = 0;
  52.         j = 0;
  53.         while (i < rules_len) {
  54.                 lmt = nstr_pbrk(rules, i, rules_len, "*?");
  55.                 if (lmt == -1) {
  56.                         lmt = rules_len;
  57.                         next = lmt;
  58.                         c = 0;
  59.                 }else {
  60.                         next = lmt + 1;
  61.                         c = rules[lmt];
  62.                 }
  63.                 len = lmt - i;
  64.                 if (len > 0) {
  65.                         if (j + len > text_len) {
  66.                                 return -1;
  67.                         }
  68.                         if (strncmp(text + j, rules + i, len) != 0) {
  69.                                 return -1;
  70.                         }
  71.                 }
  72.                 switch (c) {
  73.                 case 0:
  74.                         i = next;
  75.                         j += len;
  76.                         break;
  77.                 case '?':
  78.                         i = next;
  79.                         j += len + 1;
  80.                         if (j > text_len) {
  81.                                 return -1;
  82.                         }
  83.                         break;
  84.                 case '*':
  85.                         i = next;
  86.                         lmt = nstr_pbrk(rules, i, rules_len, "*?");
  87.                         if (lmt == -1) {
  88.                                 lmt = rules_len;
  89.                         }
  90.                         len = lmt - i;
  91.                         while (j + len <= text_len) {
  92.                                 k = nstr_nstr(text, j, text_len, rules + i, len);
  93.                                 if (k == -1) {
  94.                                         return -1;
  95.                                 }
  96.                                 j = k;
  97.                                 if (nstr_match(text + j, text_len - j, rules + i, rules_len - i) == -1) {
  98.                                         ++j;
  99.                                         continue;
  100.                                 }
  101.                                 return 0;
  102.                         }
  103.                         return -1;
  104.                 }
  105.         }
  106.         if (j < text_len) {
  107.                 return -1;
  108.         }
  109.         return 0;
  110. }

  111. int str_match(const char *text, const char *match)
  112. {
  113.         int text_len, match_len;

  114.         text_len = strlen(text);
  115.         match_len = strlen(match);
  116.         return nstr_match(text, text_len, match, match_len);
  117. }

  118. /* TESTCASE */

  119. #include <stdio.h>

  120. int test_str_match(const char *text, const char *match)
  121. {
  122.         printf("TEST: does string \"%s\" match \"%s\" ? ", text, match);
  123.         if (str_match(text, match) == 0) {
  124.                 printf("YES");
  125.         }else {
  126.                 printf("NO");
  127.         }
  128.         printf("\n");
  129.         return 0;
  130. }

  131. int main(void)
  132. {
  133.         test_str_match("abc.txt", "*");
  134.         test_str_match("abc.txt", "?");
  135.         test_str_match("abc.txt", "abc.txt?"); /* add by hellioncu@chinaunix */
  136.         test_str_match("abc.tt", "abc.t?t"); /* add by hellioncu@chinaunix */
  137.         test_str_match("abc.txt", "abc.t?t");
  138.         test_str_match("abc.txt", "abc.t?e");
  139.         test_str_match("abc.txt", "*.txt");
  140.         test_str_match("abc.txt", "*.txe");
  141.         test_str_match("abc.txt", "*.txt*");
  142.         test_str_match("abc.txt", "*.txe*");
  143.         test_str_match("abc.txt.txe3", "*.t?t*");
  144.         test_str_match("abc.txe.txt3", "*.t?t*");
  145.         test_str_match("abc.txe.txe3", "*.t?t*");
  146.         return 0;
  147. }
复制代码

论坛徽章:
324
射手座
日期:2013-08-23 12:04:38射手座
日期:2013-08-23 16:18:12未羊
日期:2013-08-30 14:33:15水瓶座
日期:2013-09-02 16:44:31摩羯座
日期:2013-09-25 09:33:52双子座
日期:2013-09-26 12:21:10金牛座
日期:2013-10-14 09:08:49申猴
日期:2013-10-16 13:09:43子鼠
日期:2013-10-17 23:23:19射手座
日期:2013-10-18 13:00:27金牛座
日期:2013-10-18 15:47:57午马
日期:2013-10-18 21:43:38
发表于 2014-07-25 10:09 |显示全部楼层
TEST: does string "abc.txt" match "*.txt?" ? YES
TEST: does string "abc.tt" match "*.t?t" ? NO

论坛徽章:
2
2015年辞旧岁徽章
日期:2015-03-03 16:54:152015年迎新春徽章
日期:2015-03-04 09:56:11
发表于 2014-07-25 10:10 |显示全部楼层
对于?和*的用法区别不太明了。需要进一步确定

论坛徽章:
2
2015年辞旧岁徽章
日期:2015-03-03 16:54:152015年迎新春徽章
日期:2015-03-04 09:56:11
发表于 2014-07-25 10:11 |显示全部楼层
*可以匹配0-MAX个。?只能匹配1个吗?

论坛徽章:
2
2015年辞旧岁徽章
日期:2015-03-03 16:54:152015年迎新春徽章
日期:2015-03-04 09:56:11
发表于 2014-07-25 10:12 |显示全部楼层
hellioncu一下就测出了矛盾。佩服

论坛徽章:
2
2015年辞旧岁徽章
日期:2015-03-03 16:54:152015年迎新春徽章
日期:2015-03-04 09:56:11
发表于 2014-07-25 10:23 |显示全部楼层
发布了一个修正版,感谢hellioncu

论坛徽章:
324
射手座
日期:2013-08-23 12:04:38射手座
日期:2013-08-23 16:18:12未羊
日期:2013-08-30 14:33:15水瓶座
日期:2013-09-02 16:44:31摩羯座
日期:2013-09-25 09:33:52双子座
日期:2013-09-26 12:21:10金牛座
日期:2013-10-14 09:08:49申猴
日期:2013-10-16 13:09:43子鼠
日期:2013-10-17 23:23:19射手座
日期:2013-10-18 13:00:27金牛座
日期:2013-10-18 15:47:57午马
日期:2013-10-18 21:43:38
发表于 2014-07-25 10:36 |显示全部楼层
cobras 发表于 2014-07-25 10:23
发布了一个修正版,感谢hellioncu


改得还挺快

论坛徽章:
2
2015年辞旧岁徽章
日期:2015-03-03 16:54:152015年迎新春徽章
日期:2015-03-04 09:56:11
发表于 2014-07-25 10:41 |显示全部楼层
既然公开了,就要对广大用户负责。

论坛徽章:
2
2015年辞旧岁徽章
日期:2015-03-03 16:54:152015年迎新春徽章
日期:2015-03-04 09:56:11
发表于 2014-07-25 11:13 |显示全部楼层
更新第3版。修正一个错误。

论坛徽章:
15
射手座
日期:2014-11-29 19:22:4915-16赛季CBA联赛之青岛
日期:2017-11-17 13:20:09黑曼巴
日期:2017-07-13 19:13:4715-16赛季CBA联赛之四川
日期:2017-02-07 21:08:572015年亚冠纪念徽章
日期:2015-11-06 12:31:58每日论坛发贴之星
日期:2015-08-04 06:20:00程序设计版块每日发帖之星
日期:2015-08-04 06:20:00程序设计版块每日发帖之星
日期:2015-07-12 22:20:002015亚冠之浦和红钻
日期:2015-07-08 10:10:132015亚冠之大阪钢巴
日期:2015-06-29 11:21:122015亚冠之广州恒大
日期:2015-05-22 21:55:412015年亚洲杯之伊朗
日期:2015-04-10 16:28:25
发表于 2014-07-25 12:41 |显示全部楼层
cobras 发表于 2014-07-25 09:40
分享一个我写的C库函数:字符串范性匹配。
可广范用于各种搜索代码中。

有正则表达式,regex,为什么还要自己弄?
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP