Lemur95's blog

A problem with strings
By Lemur95, history, 5 years ago, In English

Hi Codeforces Community! I have been struggling with a problem that I find quite hard. Unfortunately, I don't have a link to the English version. I will try to make a short description of it.

You have 2 strings A and B, of length N and M. The strings contain only lowercase Latin letters. For every substring S of B, you have to find the length of the longest common prefix of A and S. Print the sum of these lengths.

1 <= N, M <= 2 000 000
Time Limit: 1.5 seconds
Memory Limit: 32768 kbytes

Examples:

If A = aa, B = abaa, then the answer is 8. If A = aab, B = acaabada, then the answer is 32.

I tried an approach with hashes and binary searching, but I got TLE. Is there any faster way to solve this problem? Thanks in advance.

P.S.: I will explain my approach, if needed.

Hope you'll have a great day, Protroll

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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think it can be done in linear time using this.

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

    I know the KMP algorithm. I tried an approach with it, but I got TLE as well. Could you give some details?

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

      Suppose you have a string B = "abcxxx" and A = "abc"

      So the match is at index 0. Now starting with index 0 you have 6 substrings and max prefix match is 3.

      Notice now that after index 2 there won't be any increase in prefix matched. So the answer is (1,2,3,3,3,3) = (3 * 4) / 2 + (3)*3

      It is easy to see that this is just summing 1...p, where p is the max prefix matched at i and then (n-p-i) which are left, will just have p.

      So for index i the answer is : (p * (p+1)) / 2 + (n-p-i) * (p)

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

        Thanks, But I already found the formula. You need to do this for EVERY INDEX. So, how do you find p, for some i? In order to do that, I used hashes and binary searching. Your formula refers to a fixed i.

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

Can you provide the problem link?

→ Reply
»
5 years ago, # |
← Rev. 4   Vote: I like it +1 Vote: I do not like it

This problem can be solved with hashing and binary search

The following is actually the solution to a harder version were for each substring s of B find the longest prefix of s in A. Then print the sum of all these values.

This can be solved using suffix array or tree.

1)Concatenate the two strings with $ sign between them.

2) find lcp for every two adjacent pair.(This can be found in o(|a| + |b| + 1) for the whole array)

3) then you find the answer for each right and do the needed calculations depending on the values found.(you need to use next array)

This is an outline of the solution there are some details not mentioned.

complexity O(nlogn)

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

    Thanks, but I don't really understand your solution. Maybe you can show those details? Btw, I tried with hashing and binary searching, but I got TLE.

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

      did you do cumlitive sum on the hash?

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

        What is that? I never heard of it

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

          when you do binary search on the prefix you need to calculate the hash of b which you can do easily since you are moving in increasing index. Now, the problem appears when you need to find the hash of the prefix of A.

          Since you want the hash of a prefix you can just precalculate the hash of every prefix ,and use it to fint he hash of any reange.

          This explains it. Rolling Hashing

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

            Oh yeah. I used them, but still got TLE, due to long long operations. My approach is O(NlogN).

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

              Ok I'm stupid.

              This can be solved in O(n) using z-algorithm.

              I got a 100, here is the code: https://ideone.com/fQXzia

              I didn't realize the solution sooner because i kept on thinking on the harder version.

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

                Never thinked of it. Thanks a lot!

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

I think this problem can be solved with Z-algorithm.

If we create a string $$$C$$$, where $$$C = A#B$$$, then run Z-algorithm on this string, which takes $$$O(n)$$$ time, we will get for each position $$$i$$$ in it, the longest substring of $$$C$$$ which is also a prefix of $$$C$$$.

Here, if we consider the positions after $$$'#'$$$, we will get, for each position $$$j$$$ of $$$B$$$, the longest substring of $$$B$$$ which is also a prefix of $$$A$$$, let this value be $$$len_j$$$.

For each substring of $$$B$$$, that starts at $$$j$$$ and ends at or after $$$j+len_j-1$$$, we know the answer, that is $$$len_j$$$, so we add $$$len_j * NumberOfSuchSubstrings$$$ to the total answer.

For each substring of $$$B$$$, that starts at $$$j$$$ and ends befor $$$j+len_j-1$$$, the answer is the length of that substring, so we add $$$len_j*(len_j-1)/2$$$ to the total answer.

Now, I see a comment which mentioned Z-algorithm to solve this problem before, but I'll let this comment for more details.

→ Reply