「LAOI-18」今晚来我床上打 ABC

题目描述

给定一个字符串 $S$，保证所有字符为大写字母，现在你可以进行一次翻转，即选定一个非空区间，将其修改为这个区间从右往左读出的字符串，你也可以选择不翻转。

问经过一次翻转或不翻转后，这个字符串 $S$ 最少可能有多少个子串为 $\texttt{ABC}$。

输入格式

共一行，一个字符串 $S\ (1\le |S| \le 10^6)$。

其中 $|S|$ 表示字符串 $S$ 的长度。

输出格式

共一行，一个非负整数表示答案。

样例 #1

BEDABC

0

样例 #2

BEDABCBABCBED

1

提示

样例 1 解释

显然直接翻转后三个字母即可。

样例 2 解释

初始有两个 $\texttt{ABC}$，若翻转第四个到第六个字母，则会减少一个。若翻转整个字符串，则会减少两个，增加一个（中间的 $\texttt{CBA}$）。所以答案为 $1$。