XÂU KÍ TỰ - TÊN FILE CHƯƠNG TRÌNH

Câu 2.Xâu kí tự - tên file chương trình: BL2.PAS

Cho hai xâu kí tự S1 và S2 chỉ gồm các kí tự là các chữ cái tiếng Anh. Ta gọi S1 là một mẫu của

S2 nếu có thể ghép một số kí tự của S2 để được S1.

Yêu cầu: đếm số mẫu S1 được xây dựng từ S2 thỏa mãn: mỗi kí tự của S2 thuộc không quá một mẫu S1,

hai cách xây dựng một mẫu S1 từ S2 mà chỉ khác nhau vị trí ghép các kí tự được coi là một cách.

Dữ liệu vào: đọc từ file văn bản có tên BL2.INP gồm 02 dòng:

-Dòng đầu tiên, bắt đầu từ đầu dòng ghi xâu S1.

-Dòng thứ hai, bắt đầu từ đầu dòng ghi xâu S2.

Mỗi xâu kí tự có độ dài không quá 255.

Dữ liệu ra: ghi vào file văn bản BL2.OUT theo cấu trúc:

-Dòng đầu tiên ghi số nguyên S là số cách xây dựng S1 từ S2 (S=0 nếu không có cách nào).

-Nếu S≠0 thì mỗi dòng trong số S dòng tiếp theo ghi chỉ số của các kí tự trong S2 được lấy để

ghép thành một mẫu S1, các chỉ số này được ghi theo thứ tự xuất hiện của các kí tự trong xâu S1. Hai số

liên tiếp ghi cách nhau ít nhất một khoảng trống.

Ví dụ:

BL2.INP BL2.OUT

abcd

2

bcdagdhbscgahacd

4 1 2 3

12 8 10 6

Giải thích ví dụ: Ta có S1=’ABCD’, S2=’BCDAGDHBSCGAHACD’, khi đó ta có tối đa 02 mẫu S1 được

xây dựng từ các kí tự của S2 như sau:

Mẫu 1: gồm các kí tự ở các vị trí: 4, 1, 2, 3 trong S2 và theo thứ tự các kí tự xuất hiện trong S1.

Mẫu 2: gồm các kí tự ở các vị trí: 12, 8, 10, 6 trong S2 và theo thứ tự các kí tự xuất hiện trong S1.

Sau khi xây dựng xong 02 mẫu trên thì dễ thấy trong S2 không thể xây dựng thêm được mẫu S1 nào nữa.

1