CF1313E Concatenation with intersection

Vasya had three strings $ a $ , $ b $ and $ s $ , which consist of lowercase English letters. The lengths of strings $ a $ and $ b $ are equal to $ n $ , the length of the string $ s $ is equal to $ m $ . Vasya decided to choose a substring of the string $ a $ , then choose a substring of the string $ b $ and concatenate them. Formally, he chooses a segment $ [l_1, r_1] $ ( $ 1 \leq l_1 \leq r_1 \leq n $ ) and a segment $ [l_2, r_2] $ ( $ 1 \leq l_2 \leq r_2 \leq n $ ), and after concatenation he obtains a string $ a[l_1, r_1] + b[l_2, r_2] = a_{l_1} a_{l_1 + 1} \ldots a_{r_1} b_{l_2} b_{l_2 + 1} \ldots b_{r_2} $ . Now, Vasya is interested in counting number of ways to choose those segments adhering to the following conditions: - segments $ [l_1, r_1] $ and $ [l_2, r_2] $ have non-empty intersection, i.e. there exists at least one integer $ x $ , such that $ l_1 \leq x \leq r_1 $ and $ l_2 \leq x \leq r_2 $ ; - the string $ a[l_1, r_1] + b[l_2, r_2] $ is equal to the string $ s $ .

N/A

N/A

Let's list all the pairs of segments that Vasya could choose in the first example: 1. $ [2, 2] $ and $ [2, 5] $ ; 2. $ [1, 2] $ and $ [2, 4] $ ; 3. $ [5, 5] $ and $ [2, 5] $ ; 4. $ [5, 6] $ and $ [3, 5] $ ;