Lexicographically minimal string

Xem dạng PDF
Gửi bài giải
Điểm: 100,00
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 64M
Input: stdin
Output: stdout
Tác giả:
txhai12
Dạng bài
Ngôn ngữ cho phép
C, C++
Nguồn đề + test : https://www.hackerearth.com/practice/data-structures/disjoint-data-strutures/basics-of-disjoint-data-structures/practice-problems/algorithm/lexicographically-minimal-string-6edc1406/

Khi ac bài này tại judge của clb các bạn hãy thử nộp lại ở link trên, thứ nhất là ủng hộ tác giả hoặc dịch , hai và vì test ở judge ở clb là thành viên clb sinh có thể xảy ra sai sót.

Cho bạn ba chuỗi A, B và C. Độ dài của chuỗi A và B là bằng nhau. Tất cả các chuỗi chỉ chứa kí tự thường('a'-'z'). A và B có tính chất sau :

  1. Các kí tự ở cùng vị trí trong xâu A và B (A[i] và B[i]) là tương đương nhau.
  2. Nếu một kí tự a tương đương với kí tự b thì kí tự b cũng tương đương với kí tự a.
  3. Nếu kí tự a tương đương với kí tự b và kí tự b tương đương với kí tự c, thì kí tự a cũng tương đương với kí tự c.

Ví dụ :

A - "abc" B - "xcd"

Ở ví dụ trên 'a'tương đương với 'x', 'b' tương đương với 'c' và 'c' tương đương với 'd'. Theo tính chất số 3 ta có 'b' tương đương với 'd'.

Bạn có thể thay thế bất kì kí tự nào trong xâu C bằng một kí tự tương đương với nó. Bằng cách thay thế như vậy, bạn có thể tạo ra rất nhiều xâu khác nhau. Nhiệm vụ của bạn là tìm ra xâu có thứ tự từ điển thấp nhất.

Cách so sánh thứ tự từ điển 2 xâu a và b:

Nếu hai xâu bằng độ dài: gọi i là vị trí nhỏ nhất mà a[i] != b[i], nếu a[i] < b[i] thì xâu a có thứ tự từ điển thấp hơn và ngược lại

Input

Dòng 1: Xâu A. Dòng 1: Xâu B. Dòng 1: Xâu C.

Giới hạn : ~( 1 \le len(A), len(B), len(C) \le 10^5 )~

Kết quả

In ra xâu có thứ tự từ điển bé nhất có thể biến đổi từ xâu C.

Sample Input

abc
xyz
yzp

Sample Output

bcp

Bình luận

Hãy đọc nội quy trước khi bình luận.