Đoạn lặp DNA dài nhất (Repetitions)

Nguồn: CSES

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho chuỗi DNA gồm các ký tự A, C, G, T. Một đoạn lặp là các ký tự liền nhau và giống hệt nhau; không được chọn ký tự ở vị trí rời rạc. Tìm số ký tự lớn nhất trong một đoạn lặp. Bản C giải bằng getchar(), xử lý từng ký tự khi đọc, không cần mảng hay chuỗi lưu sẵn.

Input

Một dòng chứa chuỗi DNA không rỗng, không có khoảng trắng.

Output

In một số nguyên là độ dài đoạn lặp lớn nhất.

Subtask

• Subtask 1 (20%): $1\le n\le10$.
• Subtask 2 (30%): $1\le n\le10^4$.
• Subtask 3 (50%): $1\le n\le10^6$.

Ví dụ

Ví dụ 1

Input

ATTCGGGA

Output

3

Giải thích

Các đoạn A, TT, C, GGG, A có độ dài 1,2,1,3,1. Đoạn GGG dài nhất nên đáp án là 3.

Ví dụ 2

Input

AAAA

Output

4

Giải thích

Cả bốn chữ A liên tiếp tạo thành một đoạn dài 4; phải kiểm kết quả ngay cả khi hết dòng mà không đổi ký tự.