hackercupai/hackercup huggingface dataset:
When \(K = 0\), again output `YES` if and only if \(A = B\) as in chapter 1.

When \(K = 1\) and \(A = B\), it is now possible for the answer to be `YES` due to duplicates, for instance, if \(A = B = [1, 2, 1, 2]\). We will further explain how to handle this case below.

For the special case of \(N = 2\), the answer is now `YES` if \(A_1 = A_2 = B_1 = B_2\). Otherwise, the same logic from chapter 1 remains.

In the general case, checking for a rotation becomes more difficult now that duplicates are allowed. We can no longer map values to their indices as in chapter 1, since there may be multiple indices for a given value. We could try rotating \(A\) by each \(1..N\) and comparing to \(B\), but each comparison could take \(\mathcal{O}(N)\), for an overall time complexity of \(\mathcal{O}(N^2)\). A worst-case example for typical lexicographical comparison would be \(A = [1, 1, ..., 1, 2, 3]\), \(B = [1, 1, ..., 1, 3, 2]\).

One possible solution is to concatenate \(A\) with a copy of itself and search for whether \(B\) occurs as a substring using a linear time string-matching technique such as the Knuth-Morris-Pratt, Boyer-Moore, or Z algorithm. One thing to watch out for is the \(K = 1, A = B\) case above, where it's especially important to rule out cutting \(0\) or \(N\) cards. This can be done by deleting the first and last characters of \(A+A\) before searching for \(B\).

Another valid approach involves hashing. We can define some hash function \(h(v_1, v_2, ..., v_N\)\) that is sensitive to the order of its \(N\) inputs, but also supports computing the hash \(h(v_2, ..., v_N, v_1\)\) of the rotated array in \(\mathcal{O}(1)\), assuming \(h(v_1, v_2, ..., v_N\)\) is already given. We can then rotate just the hash of \(A\) one-at-a-time, comparing each to the hash of \(B\), for an overall \(\mathcal{O}(N)\) time complexity.

[See David Harmeyer's solution video here.](https://www.youtube.com/watch?v=B8ZoGe0k1-k)