protroll's blog

By protroll, history, 5 weeks ago, ,

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

• +6

 » 5 weeks ago, # |   0 I think it can be done in linear time using this.
•  » » 5 weeks ago, # ^ |   0 I know the KMP algorithm. I tried an approach with it, but I got TLE as well. Could you give some details?
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 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)*3It 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)
•  » » » » 5 weeks ago, # ^ |   0 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.
•  » » » » » 5 weeks ago, # ^ |   0 Yes do it for every i. p at i can be found using prefix function.
•  » » » » » » 5 weeks ago, # ^ |   0 I did exactly as you said. Here is the code: https://pastebin.com/hSWg2AsR. This gives TLE
 » 5 weeks ago, # |   0 Can you provide the problem link?
•  » » 5 weeks ago, # ^ |   0 As I said in the post, I don't have a link to an English version of it, but here is the original problem link: Http://varena.ro/problema/ultron You can put it into Google Translate.
 » 5 weeks ago, # | ← Rev. 4 →   +1 This problem can be solved with hashing and binary searchThe 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)
•  » » 5 weeks ago, # ^ |   0 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.
•  » » » 5 weeks ago, # ^ |   0 did you do cumlitive sum on the hash?
•  » » » » 5 weeks ago, # ^ |   0 What is that? I never heard of it
•  » » » » » 5 weeks ago, # ^ |   0 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
•  » » » » » » 5 weeks ago, # ^ |   0 Oh yeah. I used them, but still got TLE, due to long long operations. My approach is O(NlogN).
•  » » » » » » » 5 weeks ago, # ^ |   +4 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/fQXziaI didn't realize the solution sooner because i kept on thinking on the harder version.
•  » » » » » » » » 5 weeks ago, # ^ |   0 Never thinked of it. Thanks a lot!
 » 5 weeks ago, # |   +4 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.
•  » » 5 weeks ago, # ^ |   +6 Thanks, but now I know it thanks to Jester.