Prerequisites: Prefix Function/ Z-Function

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

Now, let we have computed Z-function of array CC and we get a Z-array, where z[i]z[i] represents the length of the longest common prefix between array CC and the suffix of array CC starting at ii. Here we can observe that if a prefix of length ii occurs kk times than the prefix of length i1i-1 should occur at least kk times. Let occ[i]occ[i] represents occurrence of each ii in Z-array. So, we will compute occ[i1]=occ[i1]+occ[i]occ[i-1] =occ[i-1]+ occ[i], where we will iterate through i=Ni=N to 11. Now occ[i]occ[i] will represent the occurrence of each prefix of length ii. 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 ii.

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

Solution:

  1. Setter’s solution (Prefix Function)

  2. Alter’s solution (Z-Function)

Contributors

Statistics

62% Solution Ratio
RAB_27Earliest, Jun '21
Kuddus.6068Fastest, 0.1s
rudro25Lightest, 6.0 MB
rudro25Shortest, 1075B
Toph uses cookies. By continuing you agree to our Cookie Policy.