Lời giải cho 100% bộ test bài toán mô phỏng thuật toán so khớp chuỗi KMP. Ta gọi dãy số a có độ dài \(k\) tương đương với dãy số \(b\) có độ dài \(k\) khi so sánh giá trị tại vị trí \(i\) và \(j\) có \(a[i] < a[j]\) khi và chỉ khi \(b[i] < b[j]\) với mọi \(i, j\) trong khoảng từ \(1\) đến \(k\).

Cho một dãy số \(a\) từ \(1\) đến \(k\) và \(b\) từ \(1\) đến \(k\), để kiểm tra hai dãy có tương đương khi biết dãy \(a\) từ \(1\) đến \(k-1\) tương đương với dãy \(b\) từ \(1\) đến \(k-1\), ta chỉ cần kiểm tra điều kiện \(a[q] \lt a[k]\) khi và chỉ khi \(b[q] \lt b[k]\) với mọi \(q\) từ \(1\) đến \(k-1\).

Gọi \(a[u]\) là số lớn nhất trong dãy \(a\) từ \(1\) đến \(k-1\) mà nhỏ hơn \(a[k]\) và \(a[w]\) là số nhỏ nhất trong dãy \(a\) từ \(1\) đến \(k-1\) mà lớn hơn \(a[k]\). Giả sử hai phần tử \(a[u]\) và \(a[w]\) trên tồn tại. Theo định nghĩa trên ta có \(a[u] \lt a[k] \lt a[w]\). Để kiểm tra điều kiện trên, ta chỉ cần kiểm tra \(b[u] \lt b[k] \lt b[w]\). Điều này là hiển nhiên vì dãy \(a\) từ \(1\) đến \(k-1\) tương đương với dãy \(b\) từ \(1\) đến \(k-1\) nên số lượng phần tử trong dãy \(a\) từ \(1\) đến \(k-1\) nhỏ hơn \(a[u]\) bằng với số lượng phần tử trong dãy \(b\) từ \(1\) đến \(k-1\) nhỏ hơn \(b[u]\). Tương tự, số lượng phần tử trong dãy \(a\) từ \(1\) đến \(k-1\) lớn hơn \(a[w]\) bằng với số lượng phần tử trong dãy \(b\) từ \(1\) đến \(k-1\) lớn hơn \(b[w]\).

Để tính chỉ số \(u\) và \(w\), với mỗi \(i\) từ \(1\) đến \(n\) ta cần tìm trong hoán vị \(p\) từ \(1\) đến \(i\) phần tử lớn nhất nhỏ hơn \(p[i]\), gọi phần tử này có chỉ số là \(g[i]\). Ta cũng cần biết chỉ số của phần tử nhỏ nhất lớn hơn \(p[i]\), gọi là \(h[i]\). Ta có thể tính trước các giá trị \(g[i]\) và \(h[i]\) bằng cách sử dụng danh sách liên kết đôi với độ phức tạp \(O(n)\).

Phần còn lại của lời giải: tính giá trị \(P_i\) và tìm vị trí dãy tương khớp sẽ tương tự thuật toán KMP với độ phức tạp \(O(n + m)\).