例有如下规则:
A -> B
B -> C, D
D -> C, E, F
C -> C, E, F
...
B 字串可以出现在字串 A 后面, C,D 字串可以出现在字串 B 后面, C,E,F 字串 可以出现在字串 D 后面, 以次类推。
现在给定多条数据,如 ABBCDE ACDEFF 等,如何找出符合规则的数据?
现在只想到数据结构符合图的特点,其它没有什么思路。 请问大家有什么好的思路处理这类问题吗?
1
leishi1313 2019-08-05 14:53:01 +08:00 via Android
碰到遍历,DFS+memorization 一把梭
|
2
geelaw 2019-08-05 15:01:21 +08:00
从描述看不出什么叫做“符合规则的数据”。
ABBCDE 是“符合规则的数据”吗?还是说你希望从一个字符串里找到所有满足规则的子串?例如你希望从 ABBCDE 里找出 空串、A、AB、BC、DE 这几个子串?如果出现了不是规则里的字符怎么办?例如 X,规则里没有定义 X 后面可以出现什么,也没有规定 X 本身不可以单独出现,那它是“符合规则的数据”吗? 解决了定义“找出符合规则的数据”(也就是 accepting 规则和问题类型是搜索还是判定)之后,A 等是一个字符还是一个长度不总是为 1 的字符串? 解决这类的问题的最好方法是先明白自己想要解决的问题是什么。 @leishi1313 #1 那个叫 memoization 而不是 memorization。 |
3
cirton OP @geelaw 不好意思,可能没有表述清楚。
原意是只找出符合条件的字符串(并非子串) 比如 记录 1:ABCDE, 记录 2:ABCCF, 记录 3:ABD 为符合条件的记录。 而 记录 4:ABDD ( D 后面不能跟 D ) 记录 5:ABCB ( C 后不能跟 B ) 记录 6:BCE (B 不能独立于 A 出现,因为 B 依赖于 A) 则不符合筛选条件。 |
4
doing1 2019-08-05 15:24:30 +08:00
脑细胞烧死了一只。。。
|
5
ipwx 2019-08-05 15:36:55 +08:00 via Android
搜索“ ac 自动机”
|
6
momocraft 2019-08-05 15:39:13 +08:00
“ B 依赖于 A ” 又是什么,之前完全没提到
大家都这么忙,你可以试试自己写个状态机 |
7
leishi1313 2019-08-05 15:41:50 +08:00 via Android
|
9
cirton OP @leishi1313 谢谢,我再理解一下。。
|
10
jmc891205 2019-08-05 15:55:24 +08:00
Aho – Corasick algorithm 了解一下
|
12
geelaw 2019-08-05 16:05:42 +08:00 via iPhone
@cirton #3 如果 ABCD 等都是字母,这相当于直接告诉你了一个 DFA,按照 DFA 计算就结束了。
如果 ABCD 等是正则表达式,这是告诉你一个 GNFA,可以先变换为 NFA 再计算。 |
13
wysnylc 2019-08-05 17:01:00 +08:00
正则基于 DFA 实现,明显你的需求没必要实现 DFS&BFS
如果有多种特殊需求而正则不好写,那就写多个正则 |