Bài 28.6. Khoảng Trắng Tối Thiểu - [Độ khó: Khó]

Trong một nhiệm vụ tối ưu hóa việc truyền tải dữ liệu, bạn cần tìm một "cửa sổ" (chuỗi con liên tiếp) trong một đoạn dữ liệu lớn (S) sao cho cửa sổ đó chứa tất cả các thành phần cần thiết (T) với số lượng ít nhất. Cụ thể hơn, bạn được cho hai chuỗi S và T. Bạn phải tìm chuỗi con liên tục ngắn nhất của S mà chứa tất cả các ký tự của T (có tính đến số lượng ký tự trùng lặp). Nếu T có 'a' hai lần, thì chuỗi con của S cũng phải chứa 'a' ít nhất hai lần.

INPUT FORMAT

Dòng đầu tiên chứa chuỗi S (đoạn dữ liệu lớn), độ dài không quá 100,000 ký tự. Dòng thứ hai chứa chuỗi T (các thành phần cần thiết), độ dài không quá 10,000 ký tự. Cả S và T chỉ chứa các chữ cái tiếng Anh (a-z, A-Z). Chú ý rằng 'a' và 'A' là các ký tự khác nhau.

OUTPUT FORMAT

In ra chuỗi con ngắn nhất tìm được. Nếu không có chuỗi con nào của S chứa tất cả các ký tự của T, in ra chuỗi rỗng.

Ví dụ 1:

Input:

ADOBECODEBANC
ABC

Output:

BANC

Giải thích:

• Chuỗi S là "ADOBECODEBANC", chuỗi T là "ABC".
• Các chuỗi con chứa tất cả các ký tự 'A', 'B', 'C' là:
  • "ADOBEC": chứa A, B, C. Độ dài 6.
  • "CODEBA": chứa C, O, D, E, B, A. Độ dài 6.
  • "ODEBANC": chứa O, D, E, B, A, N, C. Độ dài 7.
  • "BANC": chứa B, A, N, C. Độ dài 4.
• "BANC" là chuỗi con ngắn nhất thỏa mãn điều kiện.

Ví dụ 2:

Input:

a
a

Output:

a

Giải thích:

• Chuỗi S là "a", chuỗi T là "a".
• "a" là chuỗi con ngắn nhất chứa "a".

Ví dụ 3:

Input:

abc
bca

Output:

abc

Giải thích:

• Chuỗi S là "abc", chuỗi T là "bca".
• "abc" là chuỗi con ngắn nhất chứa 'b', 'c', 'a' theo đúng số lượng.