#include <iostream>#include <cstdio>#include <cstdlib>#include <cstring>using namespace std;template <class T>inline void gmax(T &a, T b) { if (a < b) { a = b; }}const int MAX_N = 200005;int n;char str[MAX_N];char s[MAX_N];int idx[256];int leftMost[256];int rightMost[256];long long hashLeft[MAX_N];long long hashRight[MAX_N];long long pow131[MAX_N];int getLength(int x, int y, int limit) { int l = 1, r = limit; int ans = 0; while (l <= r) { int mid = (l + r) >> 1; long long hash1 = (hashRight[x - mid + 1] - hashRight[x + 1]) * pow131[y - 1]; long long hash2 = (hashLeft[y + mid - 1] - hashLeft[y - 1]) * pow131[n - x]; if (hash1 == hash2) { ans = mid; l = mid + 1; } else { r = mid - 1; } } return ans;}int main() { for (int i = 'a'; i <= 'z'; i++) { idx[i] = i - 'a' + 1; } for (int i = 'A'; i <= 'Z'; i++) { idx[i] = i - 'A' + 27; } pow131[0] = 1; for (int i = 1; i <= 200001; i++) { pow131[i] = pow131[i - 1] * 131ll; } int cas = 0; while (scanf("%s", str + 1) != EOF) { memset(hashLeft, 0, sizeof(hashLeft)); memset(hashRight, 0, sizeof(hashRight)); memset(leftMost, 0, sizeof(leftMost)); memset(rightMost, 0, sizeof(rightMost)); n = strlen(str + 1); s[1] = idx[(int)str[1]]; for (int i = 2; i <= n; i++) { s[2 * i - 2] = 0; s[2 * i - 1] = idx[(int)str[i]]; } n = n + n - 1; for (int i = 1; i <= n; i++) { hashLeft[i] = hashLeft[i - 1] + s[i] * pow131[i - 1]; } for (int i = n; i >= 1; i--) { hashRight[i] = hashRight[i + 1] + s[i] * pow131[n - i]; } for (int i = 1; i <= n; i++) { rightMost[(int)s[i]] = i; } for (int i = n; i >= 1; i--) { leftMost[(int)s[i]] = i; } int ans = 0; for (int i = 1; i <= n; i++) { int length = min(i - 1, n - i); int length1 = getLength(i - 1, i + 1, length); int x1 = i - length1 - 1; int y1 = i + length1 + 1; int a = s[x1]; int b = s[y1]; int totLength = 0; totLength = length1; if (length1 < length) { length = min(x1 - 1, n - y1); int length2 = getLength(x1 - 1, y1 + 1, length); int x2 = x1 - length2 - 1; int y2 = y1 + length2 + 1; if (s[i] == b || s[i] == a) { gmax(totLength, length1 + 1 + length2); } if (rightMost[b] > y1) { gmax(totLength, min(y2 - 1, rightMost[b] - 1) - i); } if (leftMost[b] < x1) { gmax(totLength, i - max(x2 + 1, leftMost[b] + 1)); } if (rightMost[a] > y1) { gmax(totLength, min(y2 - 1, rightMost[a] - 1) - i); } if (leftMost[a] < x1) { gmax(totLength, i - max(x2 + 1, leftMost[a] + 1)); } if (length2 < length) { int _a = s[x2]; int _b = s[y2]; if ((_a == a && b == _b) || (_a == b && _b == a)) { length = min(x2 - 1, n - y2); int length3 = getLength(x2 - 1, y2 + 1, length); gmax(totLength, length1 + 1 + length2 + 1 + length3); } } } if (s[i]) { gmax(ans, totLength / 2 * 2 + 1); } else { gmax(ans, (totLength + 1) / 2 * 2); } } printf("Case %d: %dn", ++cas, ans); } return 0;}
