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

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

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?

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

»
10 лет назад, # |
  Проголосовать: нравится 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.

→ Ответить