SIMILARITY - Độ tương đồng
Dữ liệu vào: Standard input
Dữ liệu ra: Standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: Ngapt

Trong quá trình tìm kiếm các hành tinh có khả năng tồn tại sự sống người ta phải xác định các tham số đặc trưng cho hành tinh. 

Với 2 hành tinh mới phát hiện người ta xác định được bộ giá trị đặc trưng cho mỗi hành tinh là A = (a1, a2, . . ., an) và B = (b1, b2, . . ., bm). 

Mức độ tương đồng của 2 hành tinh là đoạn k lớn nhất các phần tử liên tiếp nhau trong mỗi dãy trùng nhau với độ chính xác hoán vị. Nói một cách khác độ giống nhau là độ dài lớn nhất của đoạn các phần tử liên tiếp nhau trong A mà bằng cách đổi chổ các phần tử trong đó ta được đoạn các phần tử liên tiếp trong B. 

Hãy xác định k và vị trí đầu của dãy con tìm được trong A và B. 

Dữ liệu: Vào từ file văn bản SIMILARITY.INP:

  •  Dòng đầu tiên chứa một số nguyên n (1 ≤ n ≤ 1 000),
  •  Dòng thứ 2 chứa n số nguyên a1, a2, . . ., an (1 ≤ ai ≤ 100000, i = 1 ÷ n),
  •  Dòng thứ 3 số nguyên m (1 ≤ m ≤ 1 000),
  •  Dòng thứ 4 chứa m số nguyên b1, b2, . . ., bm (1 ≤ bj ≤ 1e5, j = 1 ÷ m).

Kết quả: Đưa ra file văn bản SIMILARITY.OUT trên một dòng 3 số nguyên k, p và q, trong
đó k là độ dài lớn nhất của dãy con tìm được, p – vị trí đầu của dãy con trong A, q – vị trí đầu
của dãy con trong B.

Nếu không tồn tại dãy con giống nhau thì đưa ra kết quả 0 và cặp giá trị -1, -1.

 

Ví dụ

Inp:


1 2 3

2 1 3 

Out:

3 1 1

Hint: Tổng tiền tố + hàm băm

Back to Top