高分求解字符串多模式匹配问题
问题如下:
有模式列表,大概10w数量级,如:
*csdn
csdn*
*csdn*
cs*dn
......
(* 表示通配符,可匹配0个或多个)
用户输入一个字符串,比如:csdn
要求输出满足的模式列表,如:*csdn, csdn*, *csdn*, cs*dn
关键是怎么对模式列表建立数据结构, 期待各位大侠的见解!
[解决办法]
百度：
pcre
[解决办法]
是啊，找 开源C++正则库
[解决办法]
Greta，或者Boost里面的正则库，都可以。
[解决办法]
可以自己写个相似性算法，如lestin。。bk树等
[解决办法]
这个用NFA的正则会死人的... 自己转DFA, 10W模式很easy的说...
[解决办法]
对，用正则表达式
[解决办法]
《代码之美》里面有个简单正则表达式匹配的代码。
[解决办法]
用boost里面的正则库吧
[解决办法]
正则库
[解决办法]
如果你想自己写的话，给你提供一个算法：KMP算法 字符串匹配算法。
效率还是比较高的。不过没有用boost提供的正则表达式库方便。
[解决办法]
我不知道那些说NFA正则库的咋弄, 难道一个个试... 晕...
[解决办法]
boost 里有正则库
#include<boost/regex.hpp>
[解决办法]
按正则建 DFA 表, 是正途, 比如这样. 然后把 flex 干的活弄到程序里去做就是了(稍微改改flex的代码就可以了, 把状态数搞大点, 一次处理万把条模式没有问题), 不管模式数量多少, 匹配的时间复杂度是O(LN), 与模式数量无关....
$ cat f.l ; flex -o f.c f.l ; gcc -O3 f.c -lfl -o f; echo casdn csdn TMMD TAMMD | ./f%{%}%option reject caseless%%.*csdn { printf("match rule 1.\n"); REJECT; }c.*sdn { printf("match rule 2.\n"); REJECT; }cs.*dn { printf("match rule 3.\n"); REJECT; }.*TMMD { printf("match rule 4.\n"); REJECT; }T.*MMD { printf("match rule 5.\n"); REJECT; }.%%match rule 4.match rule 1.match rule 2.match rule 2.match rule 4.match rule 1.match rule 4.match rule 1.match rule 4.match rule 1.match rule 4.match rule 1.match rule 4.match rule 1.match rule 4.match rule 1.match rule 2.match rule 3.match rule 4.match rule 4.match rule 4.match rule 4.match rule 5.match rule 4.match rule 5.match rule 5.
[解决办法]