# PROBLEM LINK:

# DIFFICULTY:

MEDIUM

# PREREQUISITES:

# PROBLEM:

Given strings S_1,S_2 and X. Determine the number of ordered pairs of strings (P,Q) such that:

- P and Q are (possibly empty) prefixes of S_1 and S_2, respectively.
- String P+Q is a substring of X.

# EXPLANATION:

*You may wish to have a look at a slightly similar problem first - SSTRPREF.*

*Note: P and Q in the editorial refer exclusively to some prefix of S_1 and S_2, respectively.*

**Definition:** We call a string S *good* if it is a substring of X.

**Observation:** If P+Q is a good string, then P+Q' is also good, where Q' is some prefix string of Q.

Thus, for a fixed P, the number of Q' such that P+Q' is good = the length of the longest possible Q such that P+Q is good, plus 1 (for when Q' is empty). Summing this value over all prefix strings P gives us the answer to the problem!

Formally, let sol_i equal the largest integer x such that S_1[..i]+S_2[..x] is good. Then, our answer is equal to \sum (sol_i+1) over all valid i.

How do we calculate this array efficiently?

## Suboptimal solution

Let J_i represent the set of all indices x such that S_1[..i] is a suffix of X[..x]. That is, the J_i is set of all x such that S_1[0..i]=X[(x-i)..x].

Also, let K_x represent the length of the longest prefix of S_2 that is also a prefix of X[x..].

Then, it is easy to see that

Array K can be calculated in O(|S_2+X|) using Z-function. Using suitable preprocessing, it is possible to calculate J in worst-case, O(|S_1|+|X|^2) using KMP.

Calculating J takes a lot of time, so we need to optimise!

## Optimal solution

Let L_x represent the set of all indices i such that S_1[..i] is a suffix of X[..x]. As before, let K_x represent the length of the longest prefix of S_2 that is also a prefix of X[x..].

Then, the equation (in the previous spoiler) can be rewritten as

which is algorithmically equivalent to doing, for every x

Clearly, this doesnâ€™t improve the overall complexity (computing L is still quadratic in the worst case). But ~~I wouldnâ€™t have mentioned it if it were useless~~ there is an interesting property that can be observed in the set L_x.

**Observation:** Let a,b\ (a<b) be any two elements in set L_x. Then, S_1[..a] is a suffix of S_1[..b]. Conversely, if b\in L_x and S_1[..a] is a suffix of S_1[..b], then a\in L_x.

(The proofâ€™s of this is rather trivial, and is left to the reader as an exercise).

How is this helpful? It is easy to deduce from it, that for all x

where b_x is the greatest index such that S_1[..b_x] is a suffix of X[..x], and a_x is the greatest index such that S_1[..a_x] is a suffix of S_1[..b_x].

Then, instead of doing the following for every i,

we can do the operation on only i=b_x, and lazily mark all elements in L_{a_x} to be updated recursively (like in lazy segment trees). This approach is linear in its time complexity.

Thus, precomputing array K (using Z-function) and a_x and b_x (using KMP), we can solve the problem in linear time!

# TIME COMPLEXITY:

Running KMP and Z-function takes O(|S_1+X|) and O(|S_2+X|) respectively. Calculating the solution takes O(|X|+|S_1|+|S_2|).

Thus, the total time complexity is

per test case.

# SOLUTIONS:

Editorialistâ€™s solution can be found here

**Experimental:** For evaluation purposes, please rate the editorial (1 being poor and 5 excellent)

- 1
- 2
- 3
- 4
- 5

0 voters