- 论坛徽章:
- 2
|
本帖最后由 cobras 于 2014-07-25 11:13 编辑
分享一个我写的C库函数:字符串范性匹配。
可广范用于各种搜索代码中。
- /*
- * note:
- *
- * 1 '*' matches 0 - MAX characters
- * 2 '?' matches only 1 character
- *
- * changes:
- *
- * 1 first
- * 2 fix hellioncu@chinaunix bug (? need to match only one character)
- * 3 fix bug (text length less than rules)
- */
- #include <string.h>
- int nstr_chr(const char *s, int off, int lmt, int c)
- {
- for (; off < lmt; ++off) {
- if (s[off] == c) {
- return off;
- }
- }
- return -1;
- }
- int nstr_pbrk(const char *s, int off, int lmt, const char *chr_list)
- {
- int len;
- len = strlen(chr_list);
- for (; off < lmt; ++off) {
- if (nstr_chr(chr_list, 0, len, s[off]) != -1) {
- return off;
- }
- }
- return -1;
- }
- int nstr_nstr(const char *s, int off, int lmt, const char *text, int text_len)
- {
- lmt -= text_len;
- for (; off <= lmt; ++off) {
- if (strncmp(s + off, text, text_len) == 0) {
- return off;
- }
- }
- return -1;
- }
- int nstr_match(const char *text, int text_len, const char *rules, int rules_len)
- {
- int i, j, k;
- int lmt;
- int next;
- int len;
- int c;
- i = 0;
- j = 0;
- while (i < rules_len) {
- lmt = nstr_pbrk(rules, i, rules_len, "*?");
- if (lmt == -1) {
- lmt = rules_len;
- next = lmt;
- c = 0;
- }else {
- next = lmt + 1;
- c = rules[lmt];
- }
- len = lmt - i;
- if (len > 0) {
- if (j + len > text_len) {
- return -1;
- }
- if (strncmp(text + j, rules + i, len) != 0) {
- return -1;
- }
- }
- switch (c) {
- case 0:
- i = next;
- j += len;
- break;
- case '?':
- i = next;
- j += len + 1;
- if (j > text_len) {
- return -1;
- }
- break;
- case '*':
- i = next;
- lmt = nstr_pbrk(rules, i, rules_len, "*?");
- if (lmt == -1) {
- lmt = rules_len;
- }
- len = lmt - i;
- while (j + len <= text_len) {
- k = nstr_nstr(text, j, text_len, rules + i, len);
- if (k == -1) {
- return -1;
- }
- j = k;
- if (nstr_match(text + j, text_len - j, rules + i, rules_len - i) == -1) {
- ++j;
- continue;
- }
- return 0;
- }
- return -1;
- }
- }
- if (j < text_len) {
- return -1;
- }
- return 0;
- }
- int str_match(const char *text, const char *match)
- {
- int text_len, match_len;
- text_len = strlen(text);
- match_len = strlen(match);
- return nstr_match(text, text_len, match, match_len);
- }
- /* TESTCASE */
- #include <stdio.h>
- int test_str_match(const char *text, const char *match)
- {
- printf("TEST: does string \"%s\" match \"%s\" ? ", text, match);
- if (str_match(text, match) == 0) {
- printf("YES");
- }else {
- printf("NO");
- }
- printf("\n");
- return 0;
- }
- int main(void)
- {
- test_str_match("abc.txt", "*");
- test_str_match("abc.txt", "?");
- test_str_match("abc.txt", "abc.txt?"); /* add by hellioncu@chinaunix */
- test_str_match("abc.tt", "abc.t?t"); /* add by hellioncu@chinaunix */
- test_str_match("abc.txt", "abc.t?t");
- test_str_match("abc.txt", "abc.t?e");
- test_str_match("abc.txt", "*.txt");
- test_str_match("abc.txt", "*.txe");
- test_str_match("abc.txt", "*.txt*");
- test_str_match("abc.txt", "*.txe*");
- test_str_match("abc.txt.txe3", "*.t?t*");
- test_str_match("abc.txe.txt3", "*.t?t*");
- test_str_match("abc.txe.txe3", "*.t?t*");
- return 0;
- }
复制代码 |
|