请教一个算法问题

[zxCoder]

输入两个字符串列表

比如

a=["hello","world"]

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

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

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

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

[GuuJiang]

对 b 建立 AC 自动机

[dzdh]

顺序是一定的吗

[jiezhi]

用 b 构建 Tire ，a 里的字符串去匹配，截断后继续从头匹配。

[jiezhi]

跟这题差不多吧 https://leetcode.com/problems/word-break/

[c0xt30a]

我给一个纯粹数学的思路：

1. 将 a, b, ..., z 分别映射到不同的质数上，譬如 a-2, b-3, c-5, d-7 ...
2. 将字符串对应的质数相乘，得到一个数字表示。譬如 'abc' -> 2*3*5 = 30
3. 原问题简化为在第二个列表数字中查询能否相乘得到地一个列表中的数字

[ccagml]

'cba' ->5*3*2=30

[ccagml]

@c0xt30a 'cba' ->5*3*2=30 ？

[c0xt30a]

@ccagml 楼主没说字符顺序是否可以调换，我理解是可以调换的