trang chủ / đề bài / icpc21_mt_n

Dãy con và hoán vị của xâu

Đề bài

Mô tả

Cho hai xâu S và T, hãy tìm xâu X có thứ tự từ điển nhỏ nhất thỏa mãn đồng thời các điều kiện sau:

  • X là một dãy con của S (nhận được bằng cách xóa đi một số ký tự của S, có thể không xóa ký tự nào, và giữ nguyên thứ tự các ký tự còn lại).
  • X là một hoán vị của T (nhận được bằng cách sắp xếp lại các ký tự của T).

Dữ liệu vào

  • Dòng thứ nhất là xâu S (1≤|S|≤105).
  • Dòng thứ hai là xâu T (1≤|T|≤103).
  • Cả hai xâu chỉ gồm các chữ cái Latin in thường (từ a đến z).

Dữ liệu ra

In ra xâu X thỏa mãn các điều kiện trên. Nếu không có xâu nào như vậy, in ra −1.

Ràng buộc

  • 1≤|S|≤105, 1≤|T|≤103.
  • S và T chỉ gồm chữ cái Latin in thường.

Ví dụ

Input Output Giải thích
bcadca
dacb
badc Các dãy con của S là hoán vị của T là bcad, bcda, badc và bdca; nhỏ nhất là badc (lấy b, a, d, c ở các vị trí 1,3,4,5).
icpccentral
nccai
iccna Lấy i, c, c, n, a ở các vị trí 1,2,4,7,10.
uuuuuu
uzt
-1 S không có chữ z và chữ t.

Bình luận

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

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0