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