Gene là một đoạn kết gắn các cặp ADN, mỗi cặp ADN được đặc trưng bằng một chữ cái trong tập
{A, C, G, T}. Gene thuần chủng là là gene hình thành từ một đoạn ADN cơ sở độ dài không quá
m, được gắn kết lặp đi lặp lại nhiều lần và ở lần lặp cuối cùng có thể chỉ chứa phấn đầu của đoạn
cơ sở. Gene được mô tả dưới dạng xâu S chỉ chứa các ký tự trong tập nêu trên. Như vậy gene thuần chủng là xâu có thể biểu diễn như ghép của k đoạn cơ sở (k ≥ 0) và có thể có thêm một đoạn đầu của cơ sở.
Ví dụ, với m = 10, S = “ACATAGACATAGACATAGACA” là một gene thuần chủng vì có đoạn cơ
sở là ”ACATAG” và S = ”ACATAG” + ”ACATAG” + ”ACATAG” + “ACA”, nhưng với m = 5 thì S
không phải là gene thuần chủng.
Cho gene S độ dài n và giá trị m. Hãy xác định S có phải là gene thuần chủng hay không và đưa
ra đoạn cơ sở ngắn nhất nếu S là gene thuần chủng hoặc đưa ra thông báo “NO” trong trường hợp
ngược lại.
Dữ liệu: Vào từ file văn bản PURE.INP:
Dòng đầu tiên chứa số nguyên m (1 ≤ m ≤ 1e6),
Dòng thứ 2 chứa xâu S độ dài n chỉ chứa các ký tự trong tập đã nêu.
Kết quả: Đưa ra file văn bản PURE.OUT đoạn cơ sở ngắn nhất tìm được hoặc thông báo NO.
Inp:
10
ACATAGACATAGACATAGACA
Out:
ACATAG