VO 13 Bài 4 - Xử lý xâu

View as PDF

Submit solution

Points: 0.66 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
VNOI Online 2013 - Ngày 2 - Trần Anh Hướng Thái Huy
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Bờm là một học sinh chuyên tin. Hôm nay Bờm được thầy dạy về thứ tự từ điển và các bài toán liên quan. Sau một hồi giảng giải và định nghĩa thứ tự từ điển là gì, thầy lấy ngay một ví dụ cho lớp. Thầy viết lên bảng 2 chuỗi kí tự dài ơi là dài, và hỏi cả lớp "Chuỗi thứ nhất có thứ tự từ điển như thế nào đối với chuỗi thứ hai: đứng trước ('~<~'), đứng sau ('~>~') hay bằng nhau ('=') ???".

Cả lớp thì đang hoang mang, vì cũng chẳng có ai hiểu được định nghĩa "Thứ tự từ điển là gì?" của thầy, nói gì đến việc giải bài tập. Nhưng Bờm thì ngược lại, do đã chuẩn bị và xem bài trước ở nhà nên đã trả lời ngay được câu hỏi của thầy sau khi thấy vừa dứt lời. Bờm ngồi chơi trong lúc mọi người đang thảo luận xôn xao, nên đã tạo thêm một số ví dụ nữa về thứ tự từ điển để có thể hiểu sâu thêm về bài học. Nhìn ngay lên bảng, Bờm phát hiện từ 2 xâu trong ví dụ của thầy, Bờm có thể tự sinh ra rất nhiều ví dụ khác. Cụ thể hơn, Bờm chọn một xâu con trong xâu thứ nhất và một xâu con trong xâu thứ hai, thế là có ngay một cặp xâu để mà so sánh. Xâu con ở đây được hiểu là một dãy các ký tự liên tiếp.

Thế là Bờm liên tục sinh ra các ví dụ và trả lời chúng. Bờm càng làm càng nhạy, và trả lời các câu hỏi về thứ tự từ điển càng nhanh. Đến nỗi trong 1 giây Bờm đã có thể trả lời đến tất cả là ~10^{6}~ câu hỏi!

Yêu cầu

  • Cho ~2~ xâu kí tự ~A~ và ~B~ (chỉ gồm các kí tự từ 'a' đến 'z') và một danh sách gồm ~Q~ câu hỏi có dạng ~(l~, ~r~, ~u~, ~v)~, với ý nghĩa cần so sánh thứ tự từ điển của xâu con ~A[l \dots r]~ và ~B[u \dots v]~ (các kí tự của một xâu được đánh số từ trái qua phải, bắt đầu bằng ~1~; và ký hiệu ~A[l \dots r]~ thể hiện xâu con từ kí tự thứ ~l~ đến ~r~ của xâu ~A)~.
  • Bạn hãy viết một chương trình mô tả lại hoạt động trả lời các câu hỏi của Bờm.

Lưu ý Xâu ~a_1a_2 \dots a_n~ ~(a_{i}~ là kí tự thứ ~i~ trong xâu ~a)~ có thứ tự từ điển nhỏ hơn xâu ~b_1b_2 \dots b_m~ nếu:

  • ~n < m~ và ~a_{i} = b_{i}~ với mọi ~i~ ~(1 \leq i \leq n)~ hoặc
  • Với ~k~ ~(1 \leq k \leq min(m, n))~ là giá trị nhỏ nhất thỏa ~a_{k} \neq b_{k}~ thì ~a_{k} < b_{k}~.
  • Hai xâu có thứ tự từ điển bằng nhau nếu không thể xác định được xâu nào có thứ tự từ điển nhỏ hơn.

Input

  • Dòng đầu tiên gồm ~2~ số nguyên dương ~L_{A} L_{B}~ là độ dài của xâu ~A~ và xâu ~B~.
  • Dòng thứ hai là xâu ~A~.
  • Dòng thứ ba là xâu ~B~.
  • Dòng tư là số nguyên dương ~Q~ - số câu hỏi trong danh sách
  • ~Q~ dòng tiếp theo, mỗi dòng gồm ~4~ số nguyên dương ~l~, ~r~ ~(1 \leq l \leq r \leq L_{A})~, ~u~, ~v~ ~(1 \leq u \leq v \leq L_{B})~ mô tả một câu hỏi cần trả lời.

Output

  • Với mỗi truy vấn, in ra 1 ký tự '=', '~>~' hoặc '~<~'. Tất cả các câu trả lời được viết trên một dòng.

Giới hạn

  • Trong tất cả các test, ~|A|~, ~|B|~, ~Q \leq 10^{6}~.
  • Trong ~40~ % số test, ~|A|~, ~|B|~, ~Q \leq 10^{3}~.

Sample Input

13 14
bomthichdacau
bomthichdabanh
3
1 10 1 10
1 10 1 11
1 11 1 11

Sample Output

=<>

Comments

Please read the guidelines before commenting.



  • 9
    danghan   commented on July 20, 2022, 4:18 p.m.

    1s trả lời tận 10^6 câu hỏi =)))) Bờm mãi đỉnh