字符串操作

Question

任何人都可以幫助我解決這個問題：這不是作業，我正在準備我的技術面試。

給定一系列的N個字符串，找到一組大小爲3的重複字符串，例如 ababadefb

Answer 1

我想我們可能會因不知道完整問題而感到痛苦。我將引導你到我的一個朋友的博客，他的朋友talks about his interview with Microsoft。

Answer 2

一個簡單的解決方案是從字符串中構造一個Suffix array，對它進行排序並計算當前後綴和前一個後綴之間的最長公共前綴。現在所有長度等於或大於3的LCP都會給出答案（本例中爲aba）。

ababadefb 0 
abadefb 3 
adefb 1 
b 0 
babadefb 1 
badefb 2 
defb 0 
efb 0 
fb 0 

---

正如你可以建立從所有後綴一個Radix tree然後得到標記有長度爲3或更多的串的所有邊的備用溶液。