输入两个字符串列表
比如
a=["hello","world"]
b=["wssb","sb","he","llo","dsb","wo","rld","sb"]
a 中的字符串由 b 中的一段序列的字符串所拼接而成，要输出具体是由哪些下标的字符串拼接的，比如这个例子中，要输出
[[2,3],[5,6]]
自己想的场景，没有数据范围，不知道最优能做到什么复杂度？
This topic created in 1486 days ago, the information mentioned may be changed or developed.
 |
1
GuuJiang Jun 6, 2022 via iPhone
对 b 建立 AC 自动机
|
 |
2
dzdh Jun 6, 2022
顺序是一定的吗
|
 |
3
jiezhi Jun 6, 2022
用 b 构建 Tire ，a 里的字符串去匹配，截断后继续从头匹配。
|
|
4
jiezhi Jun 6, 2022
|
 |
5
c0xt30a Jun 7, 2022
我给一个纯粹数学的思路：
1. 将 a, b, ..., z 分别映射到不同的质数上，譬如 a-2, b-3, c-5, d-7 ... 2. 将字符串对应的质数相乘，得到一个数字表示。譬如 'abc' -> 2*3*5 = 30 3. 原问题简化为在第二个列表数字中查询能否相乘得到地一个列表中的数字 |
 |
6
f9EHtxE2UtX3fG3 Jun 7, 2022 via Android
'cba' ->5*3*2=30
|
|
7
f9EHtxE2UtX3fG3 Jun 7, 2022 via Android
@c0xt30a 'cba' ->5*3*2=30 ？
|
Select Language