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

I have a list of strings W, how to count the ways to split a string S into substrings in W?
Автор Emirosky, история, 17 месяцев назад, По-английски

I tried to solve this problem 104375H, but i have no idea about how solve this efficiently. I need some help.

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

»
17 месяцев назад, # |
← Rev. 7   Проголосовать: нравится +12 Проголосовать: не нравится

Notice that since the total length of the string list is $$$2e5$$$, there are at most $$$\sqrt{4e5} = 632$$$ distinct lengths of string from the list. Therefore, for each string length $$$L$$$, you can check whether the substring $$$[i, i + L)$$$ is from the list. From there it's just simple dp. Worst case, the time complexity would be $$$632 * |S| * log N$$$, but with some optimization it would be closer to $$$632 * |S|$$$ (in fact I think this is the time complexity of this algorithm, but I can't prove it nor finding a test case to disprove it).

My AC solution: Code

→ Ответить
  • »
    »
    17 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Why are there 632 distinct lengths? if every |word| is maximum 1e5? I can't see the submission, "You are not allowed to view the requested page". And this is my submission (TLE of course xd)

    → Ответить
    • »
      »
      »
      17 месяцев назад, # ^ |
        Проголосовать: нравится +2 Проголосовать: не нравится

      -VIBE Assume that there are more than $$$632$$$ distinct lengths. Let's call those distinct lengths $$$L_1$$$, $$$L_2$$$, ..., $$$L_n$$$, such that $$$L_1 < L_2 < ... < L_n$$$. Then the minimum sum of lengths of those strings would be $$$L_1 + L_2 + ... + L_n \leq 1 + 2 + 3 + ... + n \leq 1 + 2 + 3 + ... + 633 = 200661$$$. Therefore the number of distinct lengths should be less than $$$633$$$.

      Therefore, for each string length $$$L$$$, you can check whether the substring $$$[i,i+L)$$$ is in the list by binary searching in the list to find if there exist any string that has the same hash code as the substring.

      Then it is just simple dp.

      → Ответить
      • »
        »
        »
        »
        17 месяцев назад, # ^ |
        ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        hey it is still giving me tle.Could you please tell me what am i doing wrongsubmission

        → Ответить
        • »
          »
          »
          »
          »
          17 месяцев назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          got accepted by using unordered_set for the pair....this question has a very tight constraints...firstly i have to use two hash functions otherwise it was colliding and then this unordered set thing for pair...i didnt know that we have to use a custom hash function for using unordered_set.....overall learned many things from it

          → Ответить
  • »
    »
    17 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    could you please explain a little bit more deep

    → Ответить
»
17 месяцев назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

I am pretty sure steveonalex idea works, but another interesting way you can solve this is by making a DP over the aho corasick automaton.

→ Ответить
  • »
    »
    17 месяцев назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Yeah, I've solved problems like this in both way. I just think that my idea is way funnier, and more suitable for cyan (although it is kind of slow, so you need optimize it really hard).

    → Ответить
    • »
      »
      »
      17 месяцев назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      I agree, it is just interesting to know other solutions and maybe learn something new along the way.

      → Ответить