Блог пользователя faiyaz26

Need Hint about Solving 452E
Автор faiyaz26, 12 лет назад, По-английски

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?

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
12 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить