Emirosky's blog

I have a list of strings W, how to count the ways to split a string S into substrings in W?
By Emirosky, history, 17 months ago, In English

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

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

Comments Comments (9)
| Write comment?
»
17 months ago, # |
← Rev. 7   Vote: I like it +12 Vote: I do not like it

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

→ Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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)

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

      -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.

      → Reply
      • »
        »
        »
        »
        17 months ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

        → Reply
        • »
          »
          »
          »
          »
          17 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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

          → Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    could you please explain a little bit more deep

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

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.

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

    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).

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

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

      → Reply