请教一个算法问题

2022-06-06 16:56:43 +08:00
 zxCoder

输入两个字符串列表

比如

a=["hello","world"]

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

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

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

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

747 次点击
所在节点    问与答
8 条回复
GuuJiang
2022-06-06 17:13:06 +08:00
对 b 建立 AC 自动机
dzdh
2022-06-06 17:36:24 +08:00
顺序是一定的吗
jiezhi
2022-06-06 18:06:26 +08:00
用 b 构建 Tire ,a 里的字符串去匹配,截断后继续从头匹配。
jiezhi
2022-06-06 18:10:09 +08:00
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
2022-06-07 07:01:49 +08:00
'cba' ->5*3*2=30
ccagml
2022-06-07 07:03:09 +08:00
@c0xt30a 'cba' ->5*3*2=30 ?
c0xt30a
2022-06-07 14:42:29 +08:00
@ccagml 楼主没说字符顺序是否可以调换,我理解是可以调换的

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

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

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

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

© 2021 V2EX