#include <iostream>
#include <string.h>
#include <cctype>
using namespace std;

typedef unsigned long long ULL;
const int N = 2000010, base = 131;

char str[N];
ULL hl[N], hr[N], p[N];

ULL get(ULL h[], int l, int r)
{
    return h[r] - h[l - 1] * p[r - l + 1];
}

int main()
{
    int T = 1;
    while (scanf("%s", str + 1), strcmp(str + 1, "END"))
    {
        int n = strlen(str + 1);
        for (int i = n * 2; i; i -= 2)
        {
            str[i] = str[i / 2];
            str[i - 1] = '#';
        }
        n *= 2;
        p[0] = 1;
        for (int i = 1, j = n; i <= n; i ++, j -- )
        {
            hl[i] = hl[i - 1] * base + str[i] - 'a' + 1; 
            hr[i] = hr[i - 1] * base + str[j] - 'a' + 1;
            p[i] = p[i - 1] * base;
        }

        int res = 0;
        for (int i = 1; i <= n; i ++ )
        {
            int l = 0, r = min(i - 1, n - i);
            while (l < r)
            {
                int mid = l + r + 1 >> 1;
                if (get(hl, i - mid, i - 1) != get(hr, n - (i + mid) + 1, n - (i + 1) + 1)) r = mid - 1;
                else l = mid;
            }

            if ( isalpha(str[i - l]) ) res = max(res, l + 1);
            else res = max(res, l);
        }

        printf("Case %d: %d\n", T ++ , res);
    }

    return 0;
}

#include <iostream>
#include <cstring>

using namespace std;

const int N = 307;

int a[N], s[N];
int f[N][N];

// 记忆化搜索：dp的记忆化递归实现
int dp(int i, int j) {
    if (i == j) return 0; // 判断边界
    int &v = f[i][j];

    if (v != -1) return v;

    v = 1e8;
    for (int k = i; k <= j - 1; k ++)
        v = min(v, dp(i, k) + dp(k + 1, j) + s[j] - s[i - 1]);

    return v;
}

int main() {
    int n;
    cin >> n;

    for (int i = 1; i <= n; i ++) {
        cin >> a[i];
        s[i] += s[i - 1] + a[i];
    }

    memset(f, -1, sizeof f);

    cout << dp(1, n) << endl;


    return 0;
}

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
string a,b;
int n, m, f[N][N];
int main() {
    cin >> n >> m >> a >> b;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            f[i][j] = (a[i-1] == b[j-1]) ? max(f[i][j], f[i - 1][j - 1] + 1) 
                        : f[i][j] = max(f[i - 1][j], f[i][j - 1]); ;
    cout << f[n][m];
    return 0;
}

#include <iostream>
using namespace std;
const int N = 100010;
int n, a[N], q[N];
int main(void) {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    cin >> n;
    int len = 0;
    for (int i = 0; i < n; i ++ ) {
        cin >> a[i];
        int l = 0, r = len;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (q[mid] < a[i]) { 
                l = mid;
             } else {
                 r = mid - 1;
             }
        }
        len = max(len, r + 1);
        q[r + 1] = a[i];
    }
    cout << len;
    return 0;
}

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n, res;
int a[N], f[N];
int main(void) {
    cin >> n;
    for (int i = 1; i <= n; i ++ ) {
        cin >> a[i];
        f[i] = 1; // 只有a[i]一个数
        for (int j = 1; j < i; j ++ )
            if (a[j] < a[i])
                f[i] = max(f[i], f[j] + 1);

        res = max(res, f[i]);
    }
    cout << res;
    return 0;
}

#include <iostream>
using namespace std;
int f[1001][1001], n, arr[1001][1001];
int main(void) {
    cin >> n;
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= i; ++j) {
            cin >> arr[i][j];
        }
    }
    for(int i = n; i >= 1; --i) {
        for(int j = i; j >= 1; --j) {
            f[i][j] += max(f[i+1][j], f[i+1][j+1]) + arr[i][j];
        }
    }
    cout << f[1][1];
    return 0;
}

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110;
int f[N], v[N][N], w[N][N], s[N];
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1;i <= n;i++) {
        cin >> s[i];
        for (int j = 0;j < s[i];j++)
            cin >> v[i][j] >> w[i][j];
    }
    for (int i = 1;i <= n;++i) {
        for (int j = m;j >= 0;--j) {
            for (int k = 0;k < s[i];++k) {
                if (v[i][k] <= j) { 
                    f[j] = max(f[j], f[j - v[i][k]] + w[i][k]); 
                }
            }
        }
    }
    cout << f[m];
    return 0;
}

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
using PII = pair<int, int>; // w & v
const int N = 2010;
int f[N], n, m;
int main() {
    cin >> n >> m;
    vector<PII> Good;
    for(int i = 1; i <= n; ++i) {
        int v, w, s;
        cin >> v >> w >> s;
        //坑,k <= s
        for(int k = 1 ; k <= s ; k <<= 1) {
            s -= k;
            Good.push_back({k*w,k*v});
        }
        if(s > 0) {
            Good.push_back({s*w,s*v});
        }
    }
    //01背包优化 + 二进制
    for(auto t : Good) {
        for(int j = m ; j >= t.second ; j--) {
            f[j] = max(f[j], f[j-t.second] + t.first);
        }
    }
    cout << f[m] << "\n";
    return 0;
}

$$\rm f[i][j] = f[i-1][j-k\cdot v_i]+k\cdot w_i)_{k\in[0,s_i]}$$

#include <iostream>
using namespace std;
const int MAXN = 10000;
int f[MAXN];
int main() {
    ios::sync_with_stdio(false),cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; ++i) {
        int v, w;
        cin >> v >> w;
        for(int j = v; j <= m; ++j) {
            f[j] = max(f[j], f[j - v] + w);
        }
    }
    cout << f[m] << "\n";
    return 0;
}