little_dog's blog

Can this problem be solved without SAM ?
By little_dog, history, 9 months ago, In English

problem link.

I found a SAM solution on luogu, but it is too hard for me to learn SAM, I wonder if there exists a solution without SAM.

Problem statement

UPD: I solved it with Suffix Array, DSU, KMP, Fenwick tree and Segment tree merging in $$$\mathcal O(n \log n)$$$, Yay!

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

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

what is SAM ?

→ Reply
»
9 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Looks similar to poi05_sza

→ Reply
  • »
    »
    9 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    The problem you gave is with an additional constraint: $$$l = 1,r = n$$$ must hold. Then the vaild string $$$t$$$ is a border of string $$$s$$$ and it could be solved with suffix array :(

    → Reply
»
9 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Auto comment: topic has been updated by little_dog (previous revision, new revision, compare).

→ Reply