#SYSTEMP444. AC

AC

题目描述

小明获得了一行字符串,他想知道在不改变字符顺序的情况下,从前到后最多能组合出多少个acac?(aacc的位置可以不连续) 比如:字符串为addcadccaddcadcc,可以找到5个acac,即下标组合为(0,3)(0,6)(0,7)(4,6)4,7)(0,3)、(0,6)、(0,7)、(4,6)(4,7)

输入格式

仅一行字符串(只包含字母)。

输出格式

一个整数,字符串中找到ac的数量。

样例

addcadcc
5

提示

50%的数据:0<0<字符串长度103\le10^3; 100%的数据:0<0<字符串长度106\le 10^6