trang chủ / đề bài / cmpsub

So sánh hai đoạn xâu

Cho xâu $S$ độ dài $N$ chỉ gồm chữ cái Latin thường và $Q$ truy vấn. Mỗi truy vấn gồm bốn số nguyên $l_{1}, r_{1}, l_{2}, r_{2}$ ( $1 \leq l_{1} \leq r_{1} \leq N$ , $1 \leq l_{2} \leq r_{2} \leq N$ ): hãy cho biết hai xâu con $S [l_{1} \dots r_{1}]$ và $S [l_{2} \dots r_{2}]$ có bằng nhau hay không (giống nhau từng kí tự, và do đó có cùng độ dài).

Dữ liệu vào

Dòng đầu: hai số nguyên $N$ và $Q$ .
Dòng thứ hai: xâu $S$ độ dài $N$ .
$Q$ dòng tiếp theo, dòng thứ $i$ gồm bốn số $l_{1}, r_{1}, l_{2}, r_{2}$ mô tả một truy vấn.

Dữ liệu ra

In $Q$ dòng: với mỗi truy vấn, in YES nếu hai xâu con bằng nhau, ngược lại in NO.

Ràng buộc

$1 \leq N, Q \leq 2 \cdot 10^{5}$
$S$ chỉ gồm chữ cái Latin thường (a–z).
Các vị trí được đánh chỉ số từ $1$ .

Ví dụ

Input	Output	Giải thích
7 4 abacaba 1 3 5 7 1 2 5 6 2 4 6 7 1 1 7 7	YES YES NO YES	Với $S =$ abacaba. Q1: $S [1 . .3] =$ aba và $S [5 . .7] =$ aba bằng nhau. Q2: $S [1 . .2] =$ ab và $S [5 . .6] =$ ab bằng nhau. Q3: $S [2 . .4] =$ bac và $S [6 . .7] =$ ba khác độ dài, không bằng. Q4: hai kí tự `a` ở đầu và cuối bằng nhau.
5 3 ababa 1 3 3 5 2 4 1 3 1 5 1 5	YES NO YES	Với $S =$ ababa. Q1: $S [1 . .3] =$ aba và $S [3 . .5] =$ aba bằng nhau (hai đoạn giao tại vị trí $3$ ). Q2: $S [2 . .4] =$ bab khác $S [1 . .3] =$ aba. Q3: cả hai chính là $S$ .

Ghi chú

Hai xâu con có độ dài khác nhau hiển nhiên không bằng nhau, in NO.
Hai khoảng $[l_{1}, r_{1}]$ và $[l_{2}, r_{2}]$ có thể trùng nhau hoặc giao nhau bất kì.

Bình luận

Không có bình luận tại thời điểm này.

Nộp bài giải

Danh sách bài nộp Bài nộp tốt nhất

Điểm 4,00một phần

Giới hạn thời gian 1.0s

Python 35.0s

Giới hạn bộ nhớ 256M

Đầu vào stdin

Kết quả của bạn stdout

Dạng bài

Chưa phân loại

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, F#, Forth, Fortran, Go, Groovy, Java, Javascript, Julia, Kotlin, Lean, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, Swift, TCL, Typescript, V, Visual Basic, Zig

Đề bài

Mô tả