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
I think it can be done in linear time using this.
I know the KMP algorithm. I tried an approach with it, but I got TLE as well. Could you give some details?
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, wherepis the max prefix matched atiand then(n-p-i)which are left, will just havep.So for index
ithe answer is :(p * (p+1)) / 2 + (n-p-i) * (p)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.
Yes do it for every
i.patican be found using prefix function.I did exactly as you said. Here is the code: https://pastebin.com/hSWg2AsR. This gives TLE
Can you provide the problem link?
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.
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)
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.
did you do cumlitive sum on the hash?
What is that? I never heard of 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
Oh yeah. I used them, but still got TLE, due to long long operations. My approach is O(NlogN).
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.
Never thinked of it. Thanks a lot!
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.
Thanks, but now I know it thanks to Jester.