{"code":"choosestr","name":"Chọn xâu","description":"[user:ami] nhận được mật mã người ngoài hành tinh. Mật mã người ngoài hành tinh được viết bằng ngôn ngữ ugnmouc. Để thuận tiện cho các bạn, [user:ami] đã dịch thứ ngôn ngữ khó hiểu này sang ngôn ngữ tiếng Anh là xâu $S$. Ý nghĩa của mật mã này, các bạn không cần biết, các bạn chỉ cần kiểm tra xem mật mã này có **ngon** hay không.\r\n\r\nTiêu chuẩn **ngon** của người ngoài hành tinh cũng rất khác biệt. [user:ami] sẽ đưa cho các bạn một xâu khác, gọi là $T$. Xâu $S$ được xem là ngon nếu có thể chọn ra $K \\geq 1$ xâu con **không giao nhau** của $S$, mỗi xâu đều có độ xài $L$. Tạm gọi các xâu này là $X_1, X_2, X_3, ..., X_K$, các xâu này phải có thứ tự từ điển nhỏ hơn hoặc bằng xâu $T$ và $K \\geq C$. [user:ami] sẽ cho các bạn xâu $S$, xâu $T$ và số $C$, các bạn cần đếm số lượng số $L$ để có thể biến xâu $S$ thành **ngon**.\r\n\r\nXâu $X$ được gọi là xâu con của S nếu ta có thể xoá đi một vài kí tự đầu tiên và cuối cùng (có thể không xoá) của $S$ và thu được xâu $X$\r\n\r\n\r\n#### Input\r\n- Dòng đầu tiên chứa 2 số nguyên dương $L_S, L_T,$ và $C$ lần lượt là chiều dài xâu $S, T$ và số $C$.\r\n- Dòng tiếp theo chứa xâu $S$ có đúng $L_S$ kí tự.\r\n- Dòng cuối cùng chứa xâu $T$ có đùng $L_T$ kí tự.\r\n\r\n#### Output \r\n- In ra một số nguyên là số lượng số $L$ thoả mãn để biến xâu S thành **ngon**.\r\n\r\n\r\n#### Scoring\r\n- Subtask $1$ ($100\\%$ số điểm): $L_S, L_T, C \\leq 100000$.\r\n####Example\r\n!!! question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        2 1 2\r\n        AA\r\n        Z \r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        1\r\n        ```\r\n        \r\n    ??? warning \"Note\"\r\n        Nếu chọn L = 1, ta có chọn ra 2 xâu |A| và |A|, các xâu này có thứ tự từ điển nhỏ hơn |Z| và 2 $\\geq$ 2.\r\n\r\n        Nếu chọn L = 2, ta chỉ có thể chọn ra 1 xâu là |AA|. Mặc dù xâu |AA| có thứ tự từ điển nhỏ hơn |Z| nhưng 1 $<$ 2.\r\n\r\n        Với L $\\geq$ 3, ta không thể chọn ra xâu con nào của S. Do đó kết quả là 1, vì chỉ có 1 cách chọn L là 1.","points":500.0,"partial":true,"time_limit":1.0,"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}}