Author: bibocat12

MÔ HÌNH GIÁ -Có 10 test. Mỗi test 0.7 điểm -Đáp án: 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; < a; khi và chi khi (tương đương với) b; < bj với mọi i, j trong khoảng [1..k] Cho một dãy số a[1..k] và b[1..k], để kiểm tra hai dãy có tương đương khi biết a[1..k-1] tương đương với b[1..k-1] ta chỉ cần kiểm tra điều kiện a[q] < a[k] khi và chỉ khi b[q] <b[k] với mọi 1 ≤q<k. (1) Gọi a[u] là số lớn nhất trong trong dãy a[1..k-1] mà nhỏ hơn a[k] và a[w] là số nhỏ nhất trong dãy a[1..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] < a[k] < a[w]. Để kiểm tra điều |kiện (1), ta chỉ cần kiểm tra b[u] < b[k] < b[w]. Điều này là hiển nhiên vì dãy a[1..k-1] tưong đương với b[1..k-1] nên số lượng phần tử trong dãy a[1..k-1] nhỏ hơn a[u] bằng với số lượng phần tử trong dãy b[1..k-1] nhỏ hơn b[u]. Tương tự, |số lượng phần tử trong dãy a[1..k-1] lớn hơn a[w] bằng với số lượng phần tử trong dãy b[1..k-1] lón hơn b[w]. Để tính chi số u, w: với mỗi i (1 ≤ i ≤ n) ta cần tìm trong hoán vị p[1..i] phần tử lớn nhất nhỏ hơn p[i] gọi phần tử này có chi 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ị Pi và tìm vị trí dãy trùng khớp sẽ tương tự thuật toán KMP với độ phức tạp O(n+m).</p>