万能的 v 友，带与或的字符串规则库的匹配应该用什么算法？求推荐 java 版。

This topic created in 3763 days ago, the information mentioned may be changed or developed.

我这边的需求是要匹配规则集中的任一条，例如规则 = 『 abc && efg || 12uiksfd 』，待匹配的字符串 = 『 1287abcdfdaefgdogkaddgd 』; 规则集的规模差不多在 1 万左右的规模。常规的多模匹配算法，例如 AC 、 WM ，好像不能做这种带与或规则的匹配。不知道万能的 v 友有什么推荐？最好是 java 版的。辛苦辛苦。。。

匹配

规则

字符

Java

2 replies • 2016-07-19 20:02:39 +08:00

mx1700

Jul 19, 2016 via Android

把规则解析成普通字符串，然后在用 AC 查找

h4x3rotab

Jul 19, 2016 via iPhone

如何把规则解析成普通字符串？我没想到对于 and or 表达式这种可行的办法。

我的想法是先把所有规则里的字符串独立取出来，编号之后插入 ac 自动机，然后用 ac 匹配。每个输入串匹配之后都可以得到规则里字符串的编号。最后用编号和对应规则做一个 dfs ，或者对规则做倒排，就可以在 O(m+n)的时间里解决问题。