关于字符串匹配问题?

2019-08-05 13:51:59 +08:00
 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 等,如何找出符合规则的数据?

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

2845 次点击
所在节点    算法
13 条回复
leishi1313
2019-08-05 14:53:01 +08:00
碰到遍历,DFS+memorization 一把梭
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。
cirton
2019-08-05 15:20:22 +08:00
@geelaw 不好意思,可能没有表述清楚。
原意是只找出符合条件的字符串(并非子串)

比如
记录 1:ABCDE,
记录 2:ABCCF,
记录 3:ABD
为符合条件的记录。

记录 4:ABDD ( D 后面不能跟 D )
记录 5:ABCB ( C 后不能跟 B )
记录 6:BCE (B 不能独立于 A 出现,因为 B 依赖于 A)
则不符合筛选条件。
doing1
2019-08-05 15:24:30 +08:00
脑细胞烧死了一只。。。
ipwx
2019-08-05 15:36:55 +08:00
搜索“ ac 自动机”
momocraft
2019-08-05 15:39:13 +08:00
“ B 依赖于 A ” 又是什么,之前完全没提到

大家都这么忙,你可以试试自己写个状态机
leishi1313
2019-08-05 15:41:50 +08:00
@geelaw 谢指出,手机屏幕小联想把中间用...代替了。其实规则已经说清楚了,一个字符串中 A 后面能跟 B,B 后面能跟 C 或 D。
@cirton 这种题 leetcode 应该有原题,但我搜了半天没找到。简单说下,先把规则放进 Hashtable,如果只是判断,那就太简单了。如果是找所有满足的字符串,DFS 你的规则 table,然后把每轮遍历的结果放进一个 hashset 就好,可能要注意一下环的检测
cirton
2019-08-05 15:42:28 +08:00
@ipwx 搜索“字符串匹配算法” 看到了自动机的内容。。but 没接触过,好抽象啊。
cirton
2019-08-05 15:44:16 +08:00
@leishi1313 谢谢,我再理解一下。。
jmc891205
2019-08-05 15:55:24 +08:00
Aho – Corasick algorithm 了解一下
jmc891205
2019-08-05 15:55:41 +08:00
@jmc891205 哦刚刚 5 楼提过了
geelaw
2019-08-05 16:05:42 +08:00
@cirton #3 如果 ABCD 等都是字母,这相当于直接告诉你了一个 DFA,按照 DFA 计算就结束了。

如果 ABCD 等是正则表达式,这是告诉你一个 GNFA,可以先变换为 NFA 再计算。
wysnylc
2019-08-05 17:01:00 +08:00
正则基于 DFA 实现,明显你的需求没必要实现 DFS&BFS
如果有多种特殊需求而正则不好写,那就写多个正则

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/589181

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX