思路与算法

只剩1颗必然满足。若原环存在相邻相同字符，从该坏边切开并划分极大相邻不同的线性段。目标长度m=d+1可行，当某段的d不是周期；用前缀函数枚举边界，判断长度L-d是否为边界。若整个环相邻均不同，求最小整周期p，m可行当且仅当(m-1)不是p的倍数。

正确性说明

剩余连续段内部必须相邻不同，且首尾不同。坏边切开后所有可能段均属于某个极大段；某段所有距离d的字符相等恰好等价d为其周期，边界判定充要。全好环中所有起点均首尾相同恰好是循环平移d保持原串，循环对称的位移是最小周期的倍数。

复杂度

各段长度总和n，前缀函数和边界处理总O(n)，初始化与输出O(n)，空间O(n)；多组逐组处理。

易错点

环边也属于相邻关系。m=1单独处理。普通前缀周期只有在整除n时才是完整环周期；输出按删除数k查询剩余n-k。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
vector<int> prefix(const string &s) {
    vector<int> p(s.size());
    for (int i = 1, j = 0; i < (int)s.size(); i++) {
        while (j && s[i] != s[j])
            j = p[j - 1];
        if (s[i] == s[j])
            j++;
        p[i] = j;
    }
    return p;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    int tc = 0;
    while (cin >> s) {
        int n = s.size(), cut = -1;
        vector<int> good(n + 1);
        good[1] = 1;
        for (int i = 0; i < n; i++)
            if (s[i] == s[(i + 1) % n]) {
                cut = i;
                break;
            }
        if (cut < 0) {
            auto p = prefix(s);
            int period = n - p[n - 1];
            if (n % period)
                period = n;
            for (int len = 2; len <= n; len++)
                good[len] = (len - 1) % period != 0;
        } else {
            string a = s.substr(cut + 1) + s.substr(0, cut + 1);
            for (int l = 0; l < n;) {
                int rr = l + 1;
                while (rr < n && a[rr] != a[rr - 1])
                    rr++;
                string t = a.substr(l, rr - l);
                int L = t.size();
                auto p = prefix(t);
                vector<int> border(L + 1);
                for (int k = L; k; k = p[k - 1])
                    border[k] = 1;
                for (int d = 1; d < L; d++)
                    if (!border[L - d])
                        good[d + 1] = 1;
                l = rr;
            }
        }
        cout << "Case " << ++tc << ": ";
        for (int k = 0; k < n; k++)
            cout << good[n - k];
        cout << '\n';
    }
}