As I understood there is a algorithm ("black box") that build trie from a string by O(n) time complexity, This algorithm use pointer to the first appearance of the substring in the string. Is the a way to save the last appearance of the substring instead in O(n) time complexity?

  • $\begingroup$ Would reversing the string, creating the trie and querying for the reversed substring work? $\endgroup$ – Discrete lizard Feb 4 '18 at 15:09
  • $\begingroup$ Thanks @Discretelizard, but I'm thinking the it isn't the case. Sorry I forget to mention that I'm talking about Suffix Trie. $\endgroup$ – ChaosPredictor Feb 4 '18 at 16:06
  • 2
    $\begingroup$ If you want to understand the limitations and possibilities for modification of an algorithm, I recommend you study it in depth. I assume you're talking about Ukkonen's algorithm; it's by no means trivial, so it could take you a while. $\endgroup$ – Raphael Feb 4 '18 at 17:34
  • 1
    $\begingroup$ What use do you intend to make of the modified links? What is the problem you're actually trying to solve? $\endgroup$ – Raphael Feb 4 '18 at 17:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.