关于字符串匹配问题？

[cirton]

例有如下规则：

A -> B
B -> C, D
D -> C, E, F
C -> C, E, F
...

B 字串可以出现在字串 A 后面, C,D 字串可以出现在字串 B 后面， C,E,F 字串 可以出现在字串 D 后面， 以次类推。

现在给定多条数据，如 ABBCDE ACDEFF 等，如何找出符合规则的数据？

现在只想到数据结构符合图的特点，其它没有什么思路。 请问大家有什么好的思路处理这类问题吗？

[leishi1313]

碰到遍历，DFS+memorization 一把梭

[geelaw]

从描述看不出什么叫做“符合规则的数据”。

ABBCDE 是“符合规则的数据”吗？还是说你希望从一个字符串里找到所有满足规则的子串？例如你希望从 ABBCDE 里找出 空串、A、AB、BC、DE 这几个子串？如果出现了不是规则里的字符怎么办？例如 X，规则里没有定义 X 后面可以出现什么，也没有规定 X 本身不可以单独出现，那它是“符合规则的数据”吗？

解决了定义“找出符合规则的数据”（也就是 accepting 规则和问题类型是搜索还是判定）之后，A 等是一个字符还是一个长度不总是为 1 的字符串？

解决这类的问题的最好方法是先明白自己想要解决的问题是什么。

@leishi1313 #1 那个叫 memoization 而不是 memorization。

[cirton]

@geelaw 不好意思，可能没有表述清楚。
原意是只找出符合条件的字符串（并非子串）

比如
记录 1：ABCDE,
记录 2：ABCCF,
记录 3：ABD
为符合条件的记录。
而
记录 4：ABDD （ D 后面不能跟 D ）
记录 5：ABCB （ C 后不能跟 B ）
记录 6：BCE (B 不能独立于 A 出现，因为 B 依赖于 A)
则不符合筛选条件。

[doing1]

脑细胞烧死了一只。。。

[ipwx]

搜索“ ac 自动机”

[momocraft]

“ B 依赖于 A ” 又是什么，之前完全没提到

大家都这么忙，你可以试试自己写个状态机

[leishi1313]

@geelaw 谢指出，手机屏幕小联想把中间用...代替了。其实规则已经说清楚了，一个字符串中 A 后面能跟 B，B 后面能跟 C 或 D。
@cirton 这种题 leetcode 应该有原题，但我搜了半天没找到。简单说下，先把规则放进 Hashtable，如果只是判断，那就太简单了。如果是找所有满足的字符串，DFS 你的规则 table，然后把每轮遍历的结果放进一个 hashset 就好，可能要注意一下环的检测

[cirton]

@ipwx 搜索“字符串匹配算法” 看到了自动机的内容。。but 没接触过，好抽象啊。

[cirton]

@leishi1313 谢谢，我再理解一下。。

[jmc891205]

Aho – Corasick algorithm 了解一下

[jmc891205]

@jmc891205 哦刚刚 5 楼提过了

[geelaw]

@cirton #3 如果 ABCD 等都是字母，这相当于直接告诉你了一个 DFA，按照 DFA 计算就结束了。

如果 ABCD 等是正则表达式，这是告诉你一个 GNFA，可以先变换为 NFA 再计算。

[wysnylc]

正则基于 DFA 实现,明显你的需求没必要实现 DFS&BFS
如果有多种特殊需求而正则不好写,那就写多个正则