开发者

String operations

Can anyone help me with this question:.This is not homework,I am preparing 开发者_开发问答for my technical interview.

Given a series of N strings, find a set of repeating string of size 3 e.g. ababadefb


I think we might suffer from not knowing the full problem. I am going to direct you to a blog entry by a friend of mine where he talks about his interview with Microsoft.


A simple solution would be to construct a Suffix array from the string, sort it and compute the longest common prefix between the current suffix and the one before it. Now all LCPs of length 3 or more will give you the answer (aba in this case).

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

As an alternate solution you can build a Radix tree from all suffixes then get all edges that are labeled with strings of length 3 or more.

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜