title: Building suffix tree ACB when we already have suffix tree AB
body: <p>I recently encounter a question about suffix tree. Assume we already have a suffix tree for string S=AB, i.e., S is a concatenation of prefix A and suffix B of S. Now we want to build suffix tree U=ACB. What is the most efficient algorithm for this task so far? </p>
  
  <p>A naive way would be to rebuild U all over again, which can be done in O(|U|) time. But it will not utilize any information of suffix tree of S. Can we do better than O(|U|)? Maybe O(|C|), i.e., as good as building a suffix tree of just C?</p>
  
  <p>Thanks very much.</p>