Solve the following problem by reducing to a DAG shortest (or longest) path problem. You should be explicit about how you use the given input to algorithmically generate an adjacency list and edge weights and which vertices you are finding a shortest (or longest) path between.

Given two arrays x[1..m] and y[1..n], we wish to find the largest k for which there are indices i and j with x[i..i + k 1] = y[j..j + k 1].

For example, if x = [1, 6, 2, 3, 5, 6, 3] and y = [9, 1, 7, 6, 2, 3, 4, 5, 6, 2], then the largest k is 3, corresponding to x[2..4] = y[4..6] = [6, 2, 3]. Describe an O(mn)-time algorithm to do this