# Editorial for New Recruitment

Prerequisites: Prefix Function/ Z-Function

Explanation: Let, first of all, we are asked to find the occurrences of each prefix of array $A$ as a subarray in array $B$. We can create a new array $C = A + x + B$ (here, $x <1$ or $x>10^9$) and compute its prefix function or Z-function.

Now, let we have computed Z-function of array $C$ and we get a Z-array, where $z[i]$ represents the length of the longest common prefix between array $C$ and the suffix of array $C$ starting at $i$. Here we can observe that if a prefix of length $i$ occurs $k$ times than the prefix of length $i-1$ should occur at least $k$ times. Let $occ[i]$ represents occurrence of each $i$ in Z-array. So, we will compute $occ[i-1] =occ[i-1]+ occ[i]$, where we will iterate through $i=N$ to $1$. Now $occ[i]$ will represent the occurrence of each prefix of length $i$. Using this we can calculate the beauty value of each prefix.

Similarly, we can use prefix function to calculate the occurrence of each prefix of length $i$.

Time Complexity: For each test case, $O(N+M)$

Solution:




### Statistics

69% Solution Ratio

RAB_27Earliest, 3M ago

LUMBERJACK_MANFastest, 0.2s

Hamim_Lightest, 7.1 MB

Deshi_TouristShortest, 1122B 