Giải bài trực tuyến

Cho một xâu DNA S gồm các ký tự {A, C, G, T}. Bạn sẽ làm việc trên một xâu T, ban đầu có giá trị rỗng. Tìm số thao tác sao chép nhỏ nhất để biến T thành một xâu cho trước. Biết rằng mỗi thao tác sao chép có một trong hai dạng:

• sao chép S i j k: sao chép đoạn S[i..j] vào xâu T bắt đầu từ vị trí k
• sao chép T i j k: sao chép đoạn T[i..j] vào xâu T bắt đầu từ vị trí k

Lưu ý nếu i > j có nghĩa là ta sao chép đoạn xâu theo thứ tự ngược. Mỗi ký tự trong T chỉ được tạo ra đúng một lần, nghĩa là không được sao chép đè lên ký tự đó.

Ví dụ: Với S = “ACTG” hãy tạo T = “GTACTATTATA”

1. Tạo GT......... bằng cách sao chép và đảo xâu “TG” từ S.
2. Tạo GTAC....... bằng cách sao chép “AC” từ S.
3. Tạo GTAC...TA.. bằng cách sao chép “TA” từ T.
4. Tạo GTAC...TAAT bằng cách sao chép và đảo xâu “TA” từ T.
5. Tạo GTACAATTAAT bằng cách sao chép “AAT” từ T.

Dữ liệu

Dòng đầu tiên chứa t là số bộ test. Với mỗi test có hai dòng chứa xâu S và xâu T với độ dài không quá 18.

Kết quả

Với mỗi test, in ra số thao tác sao chép ít nhất để tạo ra T từ S, hoặc in ra "impossible" nếu không thể làm được.

Ví dụ

Dữ liệu
5
ACGT
GTAC
A
C
ACGT
TGCA
ACGT
TCGATCGA
A
AAAAAAAAAAAAAAAAAA

Kết quả
2
impossible
1
4
6