{"code":"zerogen","name":"Nghiên cứu GEN","description":"Nhà nghiên cứu sinh học, Zero đã bắt tay vào công việc nghiên cứu GEN thuần chủng.\r\n\r\nGEN 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, T, X, G}$. GEN thuần chủng là là GEN hình thành từ một đoạn ADN cơ sở, đượ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ở. GEN đượ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 GEN thuần chủng là xâu có thể biểu diễn như tổng của $k$ đoạn cơ sở  ($k \\leq 0)$ và có thể có thêm một đoạn đầu của cơ sở.\r\n\r\nVí dụ với $S$  = `AXATAGAXATAGAXATAGAXA` là một GEN thuần chủng vì có đoạn cơ sở là `AXATAG` và $S$  = `AXATAG` + `AXATAG` + `AXATAG` + `AXA`. Cho GEN $S$ độ dài $n$. Đưa ra đoạn cơ sở ngắn nhất của xâu $S$.\r\n\r\n#### Input\r\n\r\n- Gồm một dòng duy nhất chứa xâu $S$ chỉ chứa các ký tự in hoa ${A, T, X, G}$\r\n\r\n#### Output\r\n\r\n- Gồm đoạn cơ sở ngắn nhất của xâu $S$.\r\n\r\n#### Constraints\r\n\r\n - $S.size() \\leq 5.10^{6}$\r\n\r\n#### Scoring\r\n\r\n - Subtask $1$ ($50\\%$ số điểm): $S.size() \\leq 5.10^3$.\r\n - Subtask $2$ ($50\\%$ số điểm): Không có ràng buộc gì thêm.\r\n\r\n#### Example\r\n\r\n!!! question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        AXATAGAXATAGAXATAGAXA \r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        AXATAG\r\n        ```","points":400.0,"partial":true,"time_limit":0.7,"memory_limit":262144,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}