Dãy Cuốm

View as PDF

Submit solution


Points: 200 (partial)
Time limit: 2.0s
Memory limit: 256M
Input: stdin
Output: stdout

Author:
Problem types

Anh Kha và cuom1999 là một cặp huynh đệ đồng môn dưới sự chỉ dạy của sư phự ami ở bộ môn Liên Minh of Legend. Anh Kha đã lĩnh hội thành công phương thức gánh team bằng giao thức Apeliot. cuom1999 rất ghen tị. Sau một trận đấu có KDA 1/9/2, cuom1999 quyết định nhờ Anh Kha chỉ dạy bí thuật Apeliot cho mình.

Anh Kha là một thiếu niên nghiêm túc và đầy lòng trắc ẩn. Cậu nhận thấy rằng nếu chỉ đơn giản đưa bí kíp cho cuom1999, cuom1999 sẽ không thể nhớ được. Vì vậy, mỗi lần truyền thụ một bí kíp, Anh Kha sẽ đưa cho cuom1999 một xâu kí tự ~S~ chỉ chứa các kí tự trong tập {c , u , o , m , g , a , v , l}, cuom1999 sẽ thêm một kí tự cũng thuộc tập trên vào một vị trí bất kì trong xâu ~S~ sao cho số lượng xâu kí tự ~cu~ xuất hiện trong xâu ~S~ sau khi thêm là nhiều nhất. Số lượng kí tự ~cu~ này chính là khẩu quyết mà Anh Kha muốn truyền đạt.

Xâu ~cu~ được gọi là xuất hiện trong xâu ~S~ nếu sau khi xoá đi một vài hoặc không kí tự trong xâu ~S~ và ghép các kí tự còn lại theo đúng thứ tự tương đối của nó, ta thu được xâu ~cu~.

Ví dụ, xâu ~cu~ xuất hiện trong xâu ~cạcu~ nhưng không xuất hiện trong xâu ~amivippro~

Input

Dòng đầu tiên chứa ~N~ là độ dài xâu ~S~.

Dòng thứ hai chứa ~N~ kí tự thuộc xâu ~S~.

Output

Hãy in ra số lần xuất hiện nhiều nhất có thể của xâu ~cu~ sau khi thêm một kí tự bất kì vào xâu ~S~.

Sample Input 1

8
cuomgavl

Sample Output 1

2

Sample Input 2

6
cumcal

Sample Output 1

3

Giới hạn

~30~% số điểm có ~n \leq 1000~.

~30~% số điểm có ~n \leq 5000~

~40~% số điểm có ~n \leq 10^6~

Giải thích

Ở test ví dụ 1, có thể thêm kí tự u vào sau chữ ~m~ để thu được xâu ~cuomugavl~. Xâu ~cu~ xuất hiện 2 lần.

Ở test ví dụ 2, có thể thêm kí tự u vào sau chữ ~a~ để thu được xâu ~cucaul~. Xâu ~cu~ xuất hiện 3 lần.


View comments (6)

Comments


  • 2
    lagiahuy  commented on 6:37 p.m. 1 nov, 2021

    "Ví dụ, xâu cu xuất hiện trong xâu cạcu nhưng không xuất hiện trong xâu amivippro" lấy cái gì bớt tục tĩu được không bạn?


    • 1
      MinhMW100  commented on 6:44 p.m. 1 nov, 2021

      Chuẩn luôn anh bạn!


      • 1
        lagiahuy  commented on 6:45 p.m. 1 nov, 2021

        ủa anh có trong lớp thầy Tuấn không thế?


        • 1
          MinhMW100  commented on 6:47 p.m. 1 nov, 2021 edited

          Có tên"Văn Minh" Hình con cá mập


          • 1
            lagiahuy  commented on 6:48 p.m. 1 nov, 2021

            ok anh ơi, em là ng giải thích bài palindtime ấy anh


            • 1
              MinhMW100  commented on 6:49 p.m. 1 nov, 2021

              Anh biết mà! Nghe giọng là hiểu!