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

Question

让 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"]。

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

Answer 1

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

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

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

获取该索引对应的字符串

---

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