V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
cirton
V2EX  ›  算法

关于字符串匹配问题?

  •  
  •   cirton · 2019-08-05 13:51:59 +08:00 · 2866 次点击
    这是一个创建于 1962 天前的主题,其中的信息可能已经有所发展或是发生改变。

    例有如下规则:

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

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

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

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

    13 条回复    2019-08-05 17:01:00 +08:00
    leishi1313
        1
    leishi1313  
       2019-08-05 14:53:01 +08:00 via Android
    碰到遍历,DFS+memorization 一把梭
    geelaw
        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。
    cirton
        3
    cirton  
    OP
       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
        4
    doing1  
       2019-08-05 15:24:30 +08:00
    脑细胞烧死了一只。。。
    ipwx
        5
    ipwx  
       2019-08-05 15:36:55 +08:00 via Android
    搜索“ ac 自动机”
    momocraft
        6
    momocraft  
       2019-08-05 15:39:13 +08:00
    “ B 依赖于 A ” 又是什么,之前完全没提到

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

    如果 ABCD 等是正则表达式,这是告诉你一个 GNFA,可以先变换为 NFA 再计算。
    wysnylc
        13
    wysnylc  
       2019-08-05 17:01:00 +08:00
    正则基于 DFA 实现,明显你的需求没必要实现 DFS&BFS
    如果有多种特殊需求而正则不好写,那就写多个正则
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   3450 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 23ms · UTC 10:47 · PVG 18:47 · LAX 02:47 · JFK 05:47
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.