PROBLEM LINK:Author: samhenry97 Tester: ncollins Editorialist: samhenry97 DIFFICULTY:MediumHard PREREQUISITES:PROBLEM:Given a grid of integers, determine how many rows and columns have patterns of any length QUICK EXPLANATION:For each row and column, use an algorithm like Manber & Myers to compute the suffix array and LCP array. Then, get the maximum value of the LCP array, and keep a count of the maximums for every row and column. Lastly, we just need to print out the results, summing them up. EXPLANATION:OverviewThe problem comes down to computing the longest common substring within a string itself. The brute force approach should immediately be thrown out, as the time complexity is very large. There are two main approaches for finding the results. The editorial solution runs overall in logarithmic time, but the optimal solution would run in linear time. SolutionOne way to compute the longest common substring in a string itself is to use suffix arrays and longest common prefix arrays. We'll use SA and LCP to refer to these from here out. First, we run through all of the rows and columns, computing the largest LCP value. LCP values mean that in the sorted subarrays (SA), the value of the next lexicographic subarray contains The majority of the problem comes down to computing the SA and LCP. We can use many algorithms for this. To solve this problem, a logarithmic or linear algorithm is necessary. A Now, using the max LCP values for each row and column, we can compute how many rows and columns meet the requirement, There are other ways of computing the answer, but only a logarithmic solution would work. ALTERNATIVE SOLUTION:Another way of solving this problem would be to use a suffix tree. Because the alphabet size is so large, it would be very difficult to construct such a tree. If done correctly, the problem could be solved in linear time. AUTHOR'S AND TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 17 May '18, 21:36
