B: let's fix $$$i$$$ as the beginning of $$$s2$$$ and $$$j$$$ as the ending (exclusive) of $$$s3$$$. We need to count in how many ways we can set $$$s1=s2$$$ and in how many ways we can set $$$s5+s6=s2+s3$$$ and then add the product of these numbers to the answer.

Compute the z-function for each prefix (O(n^2) in total) and let $$$z[i][j]$$$ = the maximum number of characters such that $$$s[i..] = s[j..]$$$.

If $$$k$$$ is the beginning of $$$s1$$$ then we should have $$$z[k][i] \gt =i-k$$$ in order to $$$s1=s2$$$ where $$$2i-j+1\leq k \lt i$$$. If $$$x$$$ is the beginning of $$$s5$$$, then we should have $$$z[i][x]\ge j-i$$$ in order to $$$s2+s3=s5+s6$$$ where $$$x$$$ starts from $$$j+1$$$.

If we fix $$$i$$$ and we increment $$$j$$$, these two values can be updated in constant time using some precomputations.

Can someone please explain how to solve J, H and D?

I also got WA 7 at first because I mishandled the case k=0, you should check if your solution works in that case

Auto comment: topic has been updated by cristian1997 (previous revision, new revision, compare).

Auto comment: topic has been updated by cristian1997 (previous revision, new revision, compare).

B?