Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

faiyaz26's blog

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

Hello, I tried to solve this problem with Suffix Array : 452E - Three strings . 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

»
12 years ago, hide # |
 
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