这是一个创建于 1940 天前的主题，其中的信息可能已经有所发展或是发生改变。
例有如下规则：
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
如果有多种特殊需求而正则不好写,那就写多个正则 |
Select Language