algorithm - 给定一组字符串和一组子字符串作为不同的数组。如何从每个数组中找到正确的匹配项？

设 A = ["stack","overflow","algorithm"] ，B = ["gor","tac","flo"]。A 和 B 是字符串数组，其中 B 具有子字符串。

保证 B 中的每个字符串都将是 A 中只有一个字符串的子字符串，并且 A 中的每个字符串在 B 中只有一个匹配项。还要考虑 A 和 B 中的字符串数相等。

输出 B。这样 B[i] 应该是 A[i] 的子字符串。

上述示例的输出为：

B = ["tac","flo","gor"]。

我只能想到幼稚的方法。我们对上述问题有更好的解决方案吗？

标签： algorithmdata-structures

将所有字符串连接成长s度为的超字符串L=sum(len(i))，存储字符串开头的索引。

LlogL为超字符串 ( )构建后缀数组

搜索该后缀数组中的每个子字符串 (N*logL)

获取该索引对应的字符串

如果子字符串不能位于找到的位置和下一个字符串开头的索引之间，请使用另一个后缀（情况如fax/emotion/axel和正在搜索axe）