C/C++实现字符串模糊匹配
需求:
准入授权配置文件有时候分了好几个维度进行配置,例如 company|product|sys这种格式的配置:
1.配置 "sina|weibo|pusher" 表示 sina公司weibo产品pusher系统能够准入,而"sina|weibo|sign"不允许准入
2.配置 "sina|*|pusher” 表示sina公司所有产品的pusher系统都能够准入
3.配置 “*|*|pusher” 表示所有公司的所有产品的pusher系统都能够准入
…
类似还有很多场景,好了,简单的东西不扯蛋了.
实现:
面对这个需求我第一时间想的是如何设计模式串,如何快速实现功能,因为我现在写的是一个C服务,所以我首先出现在我脑海的是一大堆strchr(XXX, ‘*'), strchr(XXX, ‘|')等等东西,后面发现这个东西没有必要自己造轮子,有现成的函数可以用,那就是fnmatch.
google了一下,发现fnmatch的资料并不是很多,大部分还都是讲php函数的,所以没办法,只能自己写写测测了.
#include <iostream> #include <fnmatch.h> #include <vector> using namespace std; int main() { const char* orgin_str = "sina|weibo|pusher"; char pattern_arr[][20] = { {"sina|*|pusher"}, {"sina|*|*"}, {"*|weibo|*"}, //不能被匹配的 {"sina|pic|*"}, {"*|*|sign"}, {"*|weibo|sign"}, {"*|pic|sign"}, {"sina|pic|sign"}, {"*|*|*"} }; static int pattern_arr_size = sizeof(pattern_arr) / sizeof(pattern_arr[0]); vector<char *> vec_str; for(int i = 0; i < pattern_arr_size; i ++) { vec_str.push_back(pattern_arr[i]); } int ret; int z = 0; while(z < 1){ for(int i = 0; i < vec_str.size(); i++) { ret = fnmatch(vec_str.at(i), orgin_str, FNM_PATHNAME); if(FNM_NOMATCH == ret){ cout<<"sorry I'm failed ["<< vec_str.at(i) <<"]"<<endl; } } ++z; } }
结果:
实验一把,结果还不赖,完全满足需求:
需求满足了,我担心的还有一个问题,那就是性能,注释掉cout输出,将while z语句调至1,000,000,重新编译跑一下:
time ./fnmatch
看来效率还不错,2.1s 进行了100W次匹配,平均2us一次,性能要求也满足了...
附:上面文章只介绍了在Linux系统下直接调用系统函数fnmatch即可实现,而没有考虑在Windows在的使用。
本人这周看了下Google-glog代码,恰巧发现了一个类似fnmatch的简单实现,因此综合起来提供了一个跨平台的接口。
#ifdef OS_WINDOWS /* Bits set in the FLAGS argument to `fnmatch'. copy from fnmatch.h(linux) */ #define FNM_PATHNAME (1 << 0) /* No wildcard can ever match `/'. */ #define FNM_NOESCAPE (1 << 1) /* Backslashes don't quote special chars. */ #define FNM_PERIOD (1 << 2) /* Leading `.' is matched only explicitly. */ #define FNM_NOMATCH 1 #define fnmatch fnmatch_win /**copy from Google-glog*/ bool SafeFNMatch(const char* pattern,size_t patt_len,const char* str,size_t str_len) { size_t p = 0; size_t s = 0; while (1) { if (p == patt_len && s == str_len) return true; if (p == patt_len) return false; if (s == str_len) return p+1 == patt_len && pattern[p] == '*'; if (pattern[p] == str[s] || pattern[p] == '?') { p += 1; s += 1; continue; } if (pattern[p] == '*') { if (p+1 == patt_len) return true; do { if (SafeFNMatch(pattern+(p+1), patt_len-(p+1), str+s, str_len-s)) { return true; } s += 1; } while (s != str_len); return false; } return false; } } /**注意:Windows平台下尚未实现最后一个参数flags的功能!!!*/ int fnmatch_win(const char *pattern, const char *name, int flags = 0) { if(SafeFNMatch(pattern,strlen(pattern),name,strlen(name))) return 0; else return FNM_NOMATCH; } #else #include <fnmatch.h> #endif int main() { const char* orgin_str = "sina|weibo|pusher"; char pattern_arr[][20] = { {"sina|*|pusher"}, {"sina|*|*"}, {"*|weibo|*"}, //不能被匹配的 {"sina|pic|*"}, {"*|*|sign"}, {"*|weibo|sign"}, {"*|pic|sign"}, {"sina|pic|sign"}, {"*|*|*"} }; static int pattern_arr_size = sizeof(pattern_arr) / sizeof(pattern_arr[0]); vector<char *> vec_str; for(int i = 0; i < pattern_arr_size; i ++) { vec_str.push_back(pattern_arr[i]); } std::cout << "Origin Str: " << orgin_str << "\n\n"; int ret; for(int i = 0; i < vec_str.size(); i++) { ret = fnmatch(vec_str.at(i), orgin_str, FNM_PATHNAME); if(ret == FNM_NOMATCH) { cout<<"sorry, I'm failed: ["<< vec_str.at(i) <<"]\n"; } else { cout<<"OK, I'm success: ["<< vec_str.at(i) <<"]\n"; } } return 0; }
输出如下:
相关文章
- vector是表示可以改变大小的数组的序列容器,本文主要介绍了C++STL标准库std::vector的使用详解,文中通过示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2022-03-06
- 这篇文章主要介绍了C++中取余运算的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-23
- 这篇文章主要介绍了C++ string常用截取字符串方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- 本文通过例子,讲述了C++调用C#的DLL程序的方法,作出了以下总结,下面就让我们一起来学习吧。...2020-06-25
- 本篇文章主要介绍了C++中四种加密算法之AES源代码,小编觉得挺不错的,现在分享给大家,也给大家做个参考。...2020-04-25
- 整数拆分,指把一个整数分解成若干个整数的和。本文重点给大家介绍C++ 整数拆分方法详解,非常不错,感兴趣的朋友一起学习吧...2020-04-25
- 这篇文章主要介绍了C++中Sort函数详细解析,sort函数是algorithm库下的一个函数,sort函数是不稳定的,即大小相同的元素在排序后相对顺序可能发生改变...2022-08-18
- 这篇文章主要介绍了C++万能库头文件在vs中的安装步骤(图文),文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-23
- 这篇文章主要介绍了C++ bitset用法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- 本篇文章小编并不是为大家讲解string类型的用法,而是讲解我个人比较好奇的问题,就是string 类型占几个字节...2020-04-25
- 这篇文章主要为大家详细介绍了C++ Eigen库计算矩阵特征值及特征向量,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-04-25
- 这篇文章主要介绍了C++ pair的用法实例详解的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了VSCode C++多文件编译的简单使用方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-03-29
- 虽然C++11引入了智能指针的,但是开发人员在与内存的斗争问题上并没有解放,如果我门实用不当仍然有内存泄漏问题,其中智能指针的循环引用缺陷是最大的问题。下面通过实例代码给大家介绍c++中的循环引用,一起看看吧...2020-04-25
- 这篇文章主要给大家介绍了关于C++随机点名生成器的相关资料,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- map容器是C++ STL中的重要一员,删除map容器中value为指定元素的问题是我们经常与遇到的一个问题,下面这篇文章主要给大家介绍了关于利用C++如何删除map容器中指定值的元素的相关资料,需要的朋友可以参考借鉴,下面来一起看看吧。...2020-04-25
- 这篇文章主要介绍了C++ 约瑟夫环问题案例详解,本篇文章通过简要的案例,讲解了该项技术的了解与使用,以下就是详细内容,需要的朋友可以参考下...2021-08-15
- 这篇文章主要介绍了C++中cin的用法详细,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- 本篇文章是对C++中的常见编译错误进行了详细的分析介绍,需要的朋友参考下...2020-04-25
- 这篇文章主要介绍了c++优先队列(priority_queue)用法详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25