Longest Common Prefix


Dear @lb71104208 ,
Yes, there is a mistake in the image. I will update the article. Thank you for finding the problem.

@lb71104208 Thanks for pointing this out! I have published @elmirap 's revision, please refresh this page and take a look again.



@elmirap said in Longest Common Prefix:
to add new strings to the trie in the future which is O(n)  lenght of the string
But whenever we add a new string S_n, we only need the LCP of S_1, S_2..., S_{n1}. The LCP can't be longer, so we really don't care about the other info of S_1, S_2, ... S_{n1} except for the LCP, right?

Were you saying we also support removing some of the strings among S_1, ..., S_n? If that's the case, then using a trie to support removing strings do have an advantage. But the followup doesn't mention after deleting strings. Without the need of removing, I still don't see why a tire is necessary.

@stupidbird911 yes, exactly , you have a trie in which you can insert and delete and have a lot of LCP queries.

@yanwen4 For simplicity let's suggest that all strings has the same length m. In the worst case all strings will be equal and we call n times IndexOf. Algorithm is O( S) where S = n*m
If strings are not equal , for example leet, lees,lest common prefix decrease by 1 each time call of IndexOf doesn't return 0. Since we compare only min (prefix, Si) characters ,total number of comparison is less than S

I don't think you just call n times indexOf, because you have a whileloop. Suppose all strings are equal, when you compare s1 and s2, if s2.indexOf(s1) != 0, you will reduce the length of s1 and call s2.indexOf(s1) again, and keep going. so I thought in worst case, the time complexity is O(n*m^2). Isn't it?


Hi @elmirap Thanks for your article. It is amazing. But I am still quite confused. What does links[ch 'a'] = node; do? Furthermore, How could you ensure that each character will link to others like the chart? I cannot see the code about it. Thanks!

@ynteng Each tree node had at most 26 links, one per each alphabet charcter. links[ch 'a'] = node assign next prefix character which is stored in node as a link to current prefix. For example if we have a and next charcter from the string is s.Character sis assigned as a children of the node which contains a, e.g links[ s ''a] = new node.
On the second questino. Each node has at most 26 links, so some links wil be null