aaav
30-06-2010, 09:27
Cho N xâu ký tự khác nhau S1,..,SN (N<=100). Các xâu này chỉ gồm các chữ cái thường tiếng Anh a..z và đều có độ dài bằng nhau và bằng L<=255. Cho trước một số nguyên dương K<=255, hãy tìm một xâu H ngắn nhất sao cho có ít nhất K xâu trong số N xâu đã cho xuất hiện tại K vị trí khác nhau của H, K xâu này không nhất thiết khác nhau. ( Xâu X xuất hiện trong xâu H nếu X là một chuỗi ký tự con liên tiếp của H).
Dữ liệu vào cho bởi file XAU.INP trong đó dòng thứ nhất ghi ba số N,L,K. N dòng tiếp theo, dòng thứ I ghi từ đầu dòng xâu Si.
Kết quả ghi ra file XAU.OUT như sau: dòng thứ nhất ghi độ dài xâu H, dòng thứ hai ghi từ đầu dòng xâu H, trong k dòng tiếp theo, mỗi dòng ghi số hiệu một xâu xuất hiện trong H và vị trí trong H mà xâu đó xuất hiện.
Nếu có nhiều xâu H, chỉ cần đưa ra một xâu. Chẳng hạn trong ví dụ sau, một xâu H khác có thể là:
ieseurmaroaieseu
Ví dụ:
Inp:
8 4 7
iese
maro
vale
urma
eseu
rosu
oaie
aron
Out :
16
maroaieseurmaron
1 6
2 1
4 10
5 7
2 12
7 4
8 13
Dữ liệu vào cho bởi file XAU.INP trong đó dòng thứ nhất ghi ba số N,L,K. N dòng tiếp theo, dòng thứ I ghi từ đầu dòng xâu Si.
Kết quả ghi ra file XAU.OUT như sau: dòng thứ nhất ghi độ dài xâu H, dòng thứ hai ghi từ đầu dòng xâu H, trong k dòng tiếp theo, mỗi dòng ghi số hiệu một xâu xuất hiện trong H và vị trí trong H mà xâu đó xuất hiện.
Nếu có nhiều xâu H, chỉ cần đưa ra một xâu. Chẳng hạn trong ví dụ sau, một xâu H khác có thể là:
ieseurmaroaieseu
Ví dụ:
Inp:
8 4 7
iese
maro
vale
urma
eseu
rosu
oaie
aron
Out :
16
maroaieseurmaron
1 6
2 1
4 10
5 7
2 12
7 4
8 13