Prerequisites: Prefix Function/ Z-Function
Explanation: Let, first of all, we are asked to find the occurrences of each prefix of array as a subarray in array . We can create a new array (here, or ) and compute its prefix function or Z-function.
Now, let we have computed Z-function of array and we get a Z-array, where represents the length of the longest common prefix between array and the suffix of array starting at . Here we can observe that if a prefix of length occurs times than the prefix of length should occur at least times. Let represents occurrence of each in Z-array. So, we will compute , where we will iterate through to . Now will represent the occurrence of each prefix of length . 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 .
Time Complexity: For each test case,
Solution: