这是一个创建于 2396 天前的主题，其中的信息可能已经有所发展或是发生改变。
例有如下规则：
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 年 8 月 5 日 via Android 碰到遍历，DFS+memorization 一把梭 |
 | 2 geelaw 2019 年 8 月 5 日 从描述看不出什么叫做“符合规则的数据”。 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 年 8 月 5 日 脑细胞烧死了一只。。。 |
 | 5 ipwx 2019 年 8 月 5 日 via Android 搜索“ ac 自动机” |
 | 6 momocraft 2019 年 8 月 5 日 “ B 依赖于 A ” 又是什么，之前完全没提到 大家都这么忙，你可以试试自己写个状态机 |
| 7 leishi1313 2019 年 8 月 5 日 via Android |
| 9 cirton OP @leishi1313 谢谢，我再理解一下。。 |
 | 10 jmc891205 2019 年 8 月 5 日 Aho Corasick algorithm 了解一下 |
| 12 geelaw 2019 年 8 月 5 日 via iPhone @cirton #3 如果 ABCD 等都是字母，这相当于直接告诉你了一个 DFA，按照 DFA 计算就结束了。 如果 ABCD 等是正则表达式，这是告诉你一个 GNFA，可以先变换为 NFA 再计算。 |
 | 13 wysnylc 2019 年 8 月 5 日 正则基于 DFA 实现,明显你的需求没必要实现 DFS&BFS 如果有多种特殊需求而正则不好写,那就写多个正则 |
Select Language