faiyaz26's blog

Need Hint about Solving 452E
By faiyaz26, 10 years ago, In English

Hello, I tried to solve this problem with Suffix Array : 452E - Три строки . I have seen some solution but unable to understand the idea. Can anyone give me the idea to solve the problem using Suffix Array?

  • Vote: I like it
  • +5
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This is my rough idea:

  1. Cat three strings together (e.g. abc$bc%cbc) and compute its SA and LCP:
  2. Traverse through the SA. Assume the current string is C. For each of the three strings S and each (necessary) length L, maintain the number of suffix T of S that is already seen such that C[1...L]==T[1...L].

This is my actual code: 7273217. The numbers I maintained is put in stack<T> st;. I (unnecessarily) used binary index tree for range-modification.

→ Reply