[AdditionalFile5646.zip](file://AdditionalFile5646.zip?type=additional_file)

#5646. 「PA 2014 Final」Matryca

标签: 传统 | 时间限制: 100 ms | 内存限制: 128 MiB |

题目描述

题目译自 PA 2014 Final Matryca

比特托邦印刷厂 (BZP) 接到了一个大订单，生产目前室内设计中最流行的条纹壁纸。每卷壁纸由 $n$ 条等宽的垂直彩色条纹组成。BZP 负责壁纸的设计与印刷。客户已经预先指定了壁纸中某些条纹的颜色，而对于剩下的条纹，则允许 BZP 自行决定颜色。

在 BZP，印刷壁纸时会使用一种能够同时印刷若干连续条纹的矩阵（印刷版）。矩阵中每个条纹的颜色都是固定的，且矩阵的长度可能短于整卷壁纸。如果矩阵由 $k$ 条条纹组成，它将被放置在所有 $n-k+1$ 个可能的起始位置上进行印刷（即矩阵的条纹与壁纸的条纹重合的所有位置），每次放置都会印刷矩阵中的所有条纹。通过这种方式，壁纸上的某一条纹可能会被多次印刷。如果一个条纹被印上了不同的颜色，其最终颜色将是这些颜色的混合。

BZP 的员工们不论审美如何，首先都希望设计出一种尽可能短的矩阵来完成整卷壁纸的印刷。他们必须牢记：对于客户指定了颜色的条纹，必须使用纯色印刷，不得混入其他颜色。换句话说，在矩阵的每一次放置中，只要覆盖到了客户指定的条纹，矩阵在该位置对应的条纹颜色必须与客户指定的颜色完全一致。

输入格式

输入只有一行，包含一个由大写拉丁字母和星号（*）组成的字符串，表示壁纸的预期外观。不同的字母表示不同的条纹颜色，而星号表示客户未指定颜色的条纹。字符串的长度 $n$ 满足 $1 \leq n \leq 1000000$。

输出格式

你的程序应输出一行，包含一个整数：能够印刷出所需壁纸的矩阵的最小长度。

样例

输入

A*B*B*A

输出

6

一种长度为 $6$ 且能印刷出样例输入中壁纸（由 $7$ 条条纹组成）的矩阵是 ABBBBA。