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.
精彩评论