Dãy Cuốm

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Xem hướng dẫn
Tác giả:
ami
Dạng bài
Điểm: 1100 (p) Thời gian: 2.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

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\).

Scoring

  • Subtask \(1\) (\(30\%\) số điểm): \(n \leq 1000\).

  • Subtask \(2\) (\(30\%\) số điểm): \(n \leq 5000\)

  • Subtask \(3\) (\(40\%\) số điểm): \(n \leq 10^6\)

Example

Test 1

Input 
8
 cuomgavl
Output 
2
Note

Ở 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 2

Input 
6
cumcal
Output 
3
Note

Ở 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.

Bình luận