这是一个创建于 887 天前的主题，其中的信息可能已经有所发展或是发生改变。
输入两个字符串列表
比如
a=["hello","world"]
b=["wssb","sb","he","llo","dsb","wo","rld","sb"]
a 中的字符串由 b 中的一段序列的字符串所拼接而成，要输出具体是由哪些下标的字符串拼接的，比如这个例子中，要输出
[[2,3],[5,6]]
自己想的场景，没有数据范围，不知道最优能做到什么复杂度？
 |
1
GuuJiang 2022-06-06 17:13:06 +08:00 via iPhone
对 b 建立 AC 自动机
|
 |
2
dzdh 2022-06-06 17:36:24 +08:00
顺序是一定的吗
|
 |
3
jiezhi 2022-06-06 18:06:26 +08:00
用 b 构建 Tire ，a 里的字符串去匹配，截断后继续从头匹配。
|
|
4
jiezhi 2022-06-06 18:10:09 +08:00
|
 |
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. 原问题简化为在第二个列表数字中查询能否相乘得到地一个列表中的数字 |
 |
6
ccagml 2022-06-07 07:01:49 +08:00 via Android
'cba' ->5*3*2=30
|
Select Language