rrpaim's blog

Growing Strings [South America Regional 2010]
By rrpaim, 10 years ago, In English

Hello,

I'm having a hard time trying to solve this problem. I've already tried three different solutions, using Hash, Aho-Corasick and Suffix Array (O(n) implementation + Longest Common Prefix) respectively. However, I keep getting TLE, as the time limit is too tight and they don't use optimization flags to compile on this site.

Notice that this problem is also available on LiveArchive. I got AC there using Hash or Aho-Corasick and even managed to be among the top solutions. However, apparently there is a much faster way of solving this problem. Could anyone help me with other ideas?

Thanks!

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

»
10 years ago, # |
  Vote: I like it +6 Vote: I do not like it

As the person with the fastest solution on URI: no, there isn't a faster way. I used Aho-Corasick.

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    Great! Thanks for the answer.

    So basically I did the following: I added all the words to the Aho-Corasick's automaton, sorted them using their lengths as keys and started working with the shortest ones. For each word i, I kept a variable L[i] representing the longest subsequence such that i is the longest string in it. Finally, I run a search on string i, return IDs of strings j that are substrings of i and update L[i] = maxj{L[j] + 1}.

    Is this idea all right? If so, probably my Aho-Corasick implementation is a bit slow... Thanks!

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      Sounds like the same idea to me. Your Aho-Corasick implementation is probably slow when the compiler is used without optimizations.

      I would personally not really worry about that. Any serious competition (or online judge) will compile your code with optimization turned on anyway.

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

        Could you please show me your Aho-Corasick implementation?, I have tried the same problem but my implementation is too slow, And I have been looking for others implementations on Internet but I did not find a good one. Thank you!

        → Reply
»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

My AC solution is as follows:

We are going to build a graph where there is an edge u-v if and only if u is a substring of v. The answer to our problem is the longest path from any node in this graph, which can be easily found with dp since the graph is clearly acyclic.

To build the graph we are going to use Aho-Corasick: first, push all strings to the automata. Then, find all substrings of all strings (i think this step is O(N^2) but still gets AC) and build the graph described above. After building the graph just run a dfs from every node to compute the longest path dp.

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

    My solution runs in 1.920s (the same idea as skavurskaa).

    Consider S your current string, L the length of S, and K the number of input strings that are substring of S.

    As you want all the strings in input that are a substring of S, you can use Aho-Corasick to find them. Remember that you will always go forward on S (just changing the current node on your Trie).

    The time complexity is O( K + L ).

    Statements: Within each test case, the sum of the lengths of all strings is at most 1e6.

    So each test case runs in O(1e6).

    → Reply