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 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)


    Statistics


    69% Solution Ratio

    RAB_27Earliest, 3M ago

    LUMBERJACK_MANFastest, 0.2s

    Hamim_Lightest, 7.1 MB

    Deshi_TouristShortest, 1122B

    Toph uses cookies. By continuing you agree to our Cookie Policy.