2011-12-03 33 views
4

列表的字符串,一問才解決編程競賽以下問題(Facebook的招聘)正從子

輸入:字符串列表:

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

和句子:

"hellothisisfoobarhi" //from 1 to 1000000 character 

輸出:12 //第一個匹配的在句子(富)的索引

另一示例將是:

子串:{ 「喜」, 「喜」}

一句: 「hiJonIamSayinghihiforYou」

輸出:15 //喜索引,第二個 '喜',因爲第一個「喜」只是一招,子sentece是「喜」喜」

一個更前:

子字符串:{‘喜’,‘福’}

句子:「說foohi」

輸出:6 //順序無所謂,他們只是需要每個人的

誰知道這個問題的好算法旁邊?

+0

現在您編輯您的文章,但,前面你說「挑戰youself」。你知道答案嗎 ?如果是的話,爲什麼在這裏問。我不確定是否StackOverFlow會挑戰人。它是從你的問題得到人們的幫助。 – Jagannath

+0

不,我不知道解決方案,我正在嘗試獲得幫助來解決問題。問題具有挑戰性 –

+0

fooxbarxhi和hifoobar是否也匹配?我們是否可以承擔對子串列表進行昂貴的預處理,或者它們是否變成了? – hugomg

回答

1

構造大字符串的後綴樹 - 樹的構造是O(n),其中n是大字符串的長度。

現在你可以在O(m)時間(其中m是子串的長度)中找到任何子串的位置,方法是簡單地沿子樹向下遍歷樹 - 節點或葉,其中子串結尾會將索引對應的鍵保存到大字符串中。

通過一組子查詢找到它們在大字符串中的位置,記錄最小索引。

+0

你能更具體嗎? –

+0

我編輯了上面的描述。 –

+0

你可以使用散列表或字典,而不是前綴樹? –

相關問題