Circle of Stones

题目描述:

桌子上有 n 个石头围成一个环。每个石头都有一种颜色。每种颜色可以由小写英文字母表示，所以总共有26种颜色。不同的石头可能有相同的颜色。

如果每一对相邻的石头都是不同颜色的，则称这 n 个石头构成的环是美丽的。两个石头是相邻的充要条件是这两个石头中间没有其它石头。例如：1号和2号是相邻的，2号和3号是相邻的，……，n号和1号是相邻的。

现在，你可以从这 n 个石头中拿走一段连续的石头（可以为空），且你只能拿一次。

你的任务是对于每个 k(0≤k≤n−1) ，判断是否存在一种取石头的方案，使得在拿走 k 个连续的石头后，剩下的 n−k 个石头构成的环是美丽的。

输入格式:

输入包含多组测试数据，以EOF结束。

每组数据有一行字符串st，字符串第i位表示桌上第i个石头的颜色。设字符串st的长度为n，则 1≤n≤106 。字符串只包含小写英文字母。

输出格式:

对于每组数据，按照样例的格式输出数据编号和一个长度为 n 的字符串。

如果存在一种取石头的方案，使得在拿走 k 个连续的石头后，剩下的 n−k 个石头构成的环是美丽的，则字符串的第 k 位（由0开始编号）为1，否则为0。

样例输入:

rrg
rrrrr
brbg
abab

样例输出:

Case 1: 011
Case 2: 00001
Case 3: 1111
Case 4: 1011

提示:

【温馨提醒】

本题输入输出规模较大，请尽量避免使用Pascal语言提交本题。同时，请C++选手尽量避免使用cin/cout进行输入输出。

【数据范围与约定】

子任务1（10分）： n≤1000。

子任务2（15分）： n≤100000 ，且输入给出的 n 个石子中，任意两个相邻的石子颜色不相同。

子任务3（25分）： n≤100000。

子任务4（15分）： n≤106 ，且输入给出的 n 个石子中，任意两个相邻的石子颜色不相同。

子任务5（35分）： n≤106。

对于所有数据，数据组数均为6组。

时间限制: 1000ms
空间限制: 256MB

---