V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
zxCoder
V2EX  ›  问与答

请教一个算法问题

  •  
  •   zxCoder · 2022-06-06 16:56:43 +08:00 · 656 次点击
    这是一个创建于 662 天前的主题,其中的信息可能已经有所发展或是发生改变。

    输入两个字符串列表

    比如

    a=["hello","world"]

    b=["wssb","sb","he","llo","dsb","wo","rld","sb"]

    a 中的字符串由 b 中的一段序列的字符串所拼接而成,要输出具体是由哪些下标的字符串拼接的,比如这个例子中,要输出

    [[2,3],[5,6]]

    自己想的场景,没有数据范围,不知道最优能做到什么复杂度?

    8 条回复    2022-06-07 14:42:29 +08:00
    GuuJiang
        1
    GuuJiang  
       2022-06-06 17:13:06 +08:00 via iPhone
    对 b 建立 AC 自动机
    dzdh
        2
    dzdh  
       2022-06-06 17:36:24 +08:00
    顺序是一定的吗
    jiezhi
        3
    jiezhi  
       2022-06-06 18:06:26 +08:00
    用 b 构建 Tire ,a 里的字符串去匹配,截断后继续从头匹配。
    jiezhi
        4
    jiezhi  
       2022-06-06 18:10:09 +08:00
    c0xt30a
        5
    c0xt30a  
       2022-06-07 02:45:21 +08:00
    我给一个纯粹数学的思路:

    1. 将 a, b, ..., z 分别映射到不同的质数上,譬如 a-2, b-3, c-5, d-7 ...
    2. 将字符串对应的质数相乘,得到一个数字表示。譬如 'abc' -> 2*3*5 = 30
    3. 原问题简化为在第二个列表数字中查询能否相乘得到地一个列表中的数字
    ccagml
        6
    ccagml  
       2022-06-07 07:01:49 +08:00 via Android
    'cba' ->5*3*2=30
    ccagml
        7
    ccagml  
       2022-06-07 07:03:09 +08:00 via Android
    @c0xt30a 'cba' ->5*3*2=30 ?
    c0xt30a
        8
    c0xt30a  
       2022-06-07 14:42:29 +08:00
    @ccagml 楼主没说字符顺序是否可以调换,我理解是可以调换的
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   4935 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 29ms · UTC 09:41 · PVG 17:41 · LAX 02:41 · JFK 05:41
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.