Băm xáo trộn

Điểm: 2,00 (OI)

Giới hạn thời gian: 2.0s

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

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

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

Một dịch vụ web lưu mật khẩu dưới dạng "hash" theo thuật toán sau:

Lấy mật khẩu $p$ (gồm các chữ cái Latin in thường), hoán vị ngẫu nhiên các kí tự trong $p$ để được xâu $p^{'}$ ( $p^{'}$ có thể trùng $p$ ).
Sinh ngẫu nhiên hai xâu chữ cái Latin in thường $s_{1}$ và $s_{2}$ (mỗi xâu có thể rỗng).
Hash thu được là $h = s_{1} + p^{'} + s_{2}$ (nối xâu).

Ví dụ, với $p =$ abacaba, có thể có $p^{'} =$ aabcaab, $s_{1} =$ zyx, $s_{2} =$ kjh, dẫn tới $h =$ zyxaabcaabkjh.

Cho mật khẩu $p$ và hash $h$ , hãy kiểm tra xem $h$ có thể là hash hợp lệ của $p$ hay không.

Bạn cần xử lý $t$ test độc lập.

Dữ liệu vào

Dòng đầu chứa số nguyên $t$ ( $1 \leq t \leq 100$ ) — số lượng test.
Với mỗi test:
- Dòng thứ nhất chứa xâu khác rỗng $p$ gồm các chữ cái Latin in thường, độ dài không quá $100$ .
- Dòng thứ hai chứa xâu khác rỗng $h$ gồm các chữ cái Latin in thường, độ dài không quá $100$ .

Dữ liệu ra

Với mỗi test, in ra một dòng chứa YES nếu $h$ có thể là hash của $p$ , và NO trong trường hợp ngược lại.

Ví dụ

Input	Output	Giải thích
5 abacaba zyxaabcaabkjh onetwothree threetwoone one zzonneyy one none twenty ten	YES YES NO YES NO	Test 1: $h =$ zyx + aabcaab + kjh, với aabcaab là một hoán vị của abacaba. Test 2: $s_{1}$ và $s_{2}$ đều rỗng, threetwoone là hoán vị của onetwothree. Test 4: $s_{1} =$ n, $s_{2}$ rỗng, và $p^{'}$ trùng $p$ .
2 abacaba zyxaabcaabkjh onetwothree threetwnone	YES NO	Test 2: trong threetwnone không có chữ o nhưng onetwothree có hai chữ o, nên không thể là hoán vị.

Bình luận

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