Xâu con chia hết cho 4 (5 điểm)

Trong tiết học về xâu kí tự. Bờm được Thầy giao nhiệm vụ giải bài toán: Cho một xâu s gồm các chữ số. Nhiệm vụ của bạn là tìm những xâu con mà chia hết cho 4. Một xâu con có thể bắt đầu bằng 0. Một xâu con của một xâu là một dãy không rỗng các kí tự liên tiếp nhau trong xâu s.

Cho ví dụ, nếu xâu s là 124 thì ta sẽ có 4 xâu chia hết cho 4 là 12,4,24, và 124. Với xâu 04 thì câu trả lời là 3: 0,4,04.

Bờm đã nghĩ ra cách giải tối ưu cho bài toán. Bạn hãy giúp Bờm kiểm chứng cách giải đó nhé.

Dữ liệu: Vào từ file văn bản divisible4.INP chứa xâu s (độ dài của xâu s từ 1 tới 3*10⁵).

Kết quả: ghi ra file văn bản divisible4.OUT đưa ra số nguyên a, số những xâu con của xâu s mà chia hết cho 4

Ràng buộc: Mỗi số nguyên cách nhau một dấu cách.

• Có 60% số test: ứng với xâu có độ dài ≤ 10³;
• Có 40% số test còn lại ứng với xâu có độ dài ≤ 3*10⁵.