string - 从子字符串列表中获取字符串

Question

我要求在编程竞赛(facebook 招聘)中解决以下问题

输入:子字符串列表:

{"bar","foo","hi"} //from 1 to 100 sub-strings 

和句子:

"hellothisisfoobarhi" //from 1 to 1000000 character

输出:12//句子中第一个匹配的索引(foo)

另一个例子是:

子字符串:{"hi","hi"}

句子:“hiJonIamSayinghihiforYou”

output:15//hi的索引，第二个'hi'因为第一个'hi'只是一个技巧，子句是'hi' hi"

还有一个例子:

子字符串:{"hi","foo"}

句子:“sayingfoohi”

output:6//顺序无关紧要，它们只需要彼此相邻

谁知道解决这个问题的好算法？

Answer 1

构建大字符串的后缀树——树的构建复杂度为 O(n)，其中 n 是大字符串的长度。

现在您可以在 O(m) 时间内找到任何子串的位置(其中 m 是子串的长度)，只需沿着子串向下穿过树——子串结束的节点或叶子将索引对应的键保存到大字符串中。

遍历子字符串集，找到它们在大字符串中的位置，跟踪最小索引。