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

江湖救急...一个字符串匹配的算法问题.

  •  
  •   Nirlan · 2018-08-30 18:00:08 +08:00 · 3118 次点击
    这是一个创建于 2038 天前的主题,其中的信息可能已经有所发展或是发生改变。

    RT.

    已知一个长字符串,比如说一篇 5000 字的文章 content ,就是说这个 content 比较长

    一组子字符串数组 如 ["北京","上海","深圳"] 就是说 每个子字符串很短

    现在想找一个时间和空间复杂度最低的算法,来判断每个子字符串是否在文章中出现过

    请各位大佬给个思路.

    15 条回复    2018-09-03 15:16:47 +08:00
    catinred
        1
    catinred  
       2018-08-30 18:02:11 +08:00
    快要交暑假作业了吧?
    Nirlan
        2
    Nirlan  
    OP
       2018-08-30 18:03:02 +08:00
    @catinred #1 额...并不是...
    napsterwu
        3
    napsterwu  
       2018-08-30 18:12:51 +08:00 via iPhone
    没必要,全遍历一遍也就 O(n),优化有啥意思?要一个词出现,用 kmp。要都出现,用 BitSet 建过滤器。
    rrfeng
        4
    rrfeng  
       2018-08-30 18:13:30 +08:00 via Android
    5000 字要什么性能?
    iblislsy
        5
    iblislsy  
       2018-08-30 18:14:44 +08:00
    @catinred 萧峰,小跳,葵花三式
    Nirlan
        6
    Nirlan  
    OP
       2018-08-30 18:18:19 +08:00 via Android
    @rrfeng 哦,像这样的 content 有几百万个
    GtDzx
        7
    GtDzx  
       2018-08-30 18:21:37 +08:00
    有个叫 AC 自动机的东西,你可以搜一下看看
    Nirlan
        8
    Nirlan  
    OP
       2018-08-30 18:22:11 +08:00 via Android
    @GtDzx 感谢,我看一下
    vizee
        9
    vizee  
       2018-08-30 18:33:46 +08:00
    关键词: 多模匹配, 字典树, 前缀树, AC 自动机, DFA, 考虑时间空间: 双数组 AC 自动机
    leriou
        10
    leriou  
       2018-08-30 18:54:15 +08:00
    DFA
    dongyx
        11
    dongyx  
       2018-08-30 22:33:43 +08:00 via iPhone
    AC 自动机
    crayygy
        12
    crayygy  
       2018-08-30 23:06:48 +08:00 via iPhone
    曾经用 AC 解决了一个性能问题,研究一下还是不错的
    vjnjc
        13
    vjnjc  
       2018-08-30 23:52:13 +08:00 via Android
    感觉用 hashmap(string, boolean)足矣。
    要的还感觉不够的话用类似 bitset 的方式,想办法把 string 转 int/long,然后用 boolean 判断是否已经存在,因为你要所有字符是否出现都要存储没啥特别优秀的方法。
    (外行人出点馊主意~
    ronglexie
        14
    ronglexie  
       2018-08-30 23:56:27 +08:00
    Trie 树
    brucewuio
        15
    brucewuio  
       2018-09-03 15:16:47 +08:00
    才 5000 字节遍历 岂不美哉
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3568 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 10:32 · PVG 18:32 · LAX 03:32 · JFK 06:32
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.