永远的零

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define F(x) ((x)/3+((x)%3==1?0:tb))
#define G(x) ((x)<tb?(x)*3+1:((x)-tb)*3+2)
const int MAXN = 1000000 + 5;
int wa[MAXN], wb[MAXN], wv[MAXN], WS[MAXN];
int c0(int *r, int a, int b) {
    return r[a] == r[b] && r[a + 1] == r[b + 1] && r[a + 2] == r[b + 2];
}
int c12(int k, int *r, int a, int b) {
    if (k == 2) return r[a]<r[b] || r[a] == r[b] && c12(1, r, a + 1, b + 1);
    else return r[a]<r[b] || r[a] == r[b] && wv[a + 1]<wv[b + 1];
}
void sort(int *r, int *a, int *b, int n, int m) {
    int i;
    for (i = 0; i<n; i++) wv[i] = r[a[i]];
    for (i = 0; i<m; i++) WS[i] = 0;
    for (i = 0; i<n; i++) WS[wv[i]]++;
    for (i = 1; i<m; i++) WS[i] += WS[i - 1];
    for (i = n - 1; i >= 0; i--) b[--WS[wv[i]]] = a[i];
    return;
}
void dc3(int *r, int *sa, int n, int m) {
    int i, j, *rn = r + n, *san = sa + n, ta = 0, tb = (n + 1) / 3, tbc = 0, p;
    r[n] = r[n + 1] = 0;
    for (i = 0; i<n; i++) if (i % 3 != 0) wa[tbc++] = i;
    sort(r + 2, wa, wb, tbc, m);
    sort(r + 1, wb, wa, tbc, m);
    sort(r, wa, wb, tbc, m);
    for (p = 1, rn[F(wb[0])] = 0, i = 1; i<tbc; i++)
        rn[F(wb[i])] = c0(r, wb[i - 1], wb[i]) ? p - 1 : p++;
    if (p<tbc) dc3(rn, san, tbc, p);
    else for (i = 0; i<tbc; i++) san[rn[i]] = i;
    for (i = 0; i<tbc; i++) if (san[i]<tb) wb[ta++] = san[i] * 3;
    if (n % 3 == 1) wb[ta++] = n - 1;
    sort(r, wb, wa, ta, m);
    for (i = 0; i<tbc; i++) wv[wb[i] = G(san[i])] = i;
    for (i = 0, j = 0, p = 0; i<ta && j<tbc; p++)
        sa[p] = c12(wb[j] % 3, r, wa[i], wb[j]) ? wa[i++] : wb[j++];
    for (; i<ta; p++) sa[p] = wa[i++];
    for (; j<tbc; p++) sa[p] = wb[j++];
    return;
}
void calcheight(int *str, int *sa, int *rnk, int *h, int n) {
    int i, j;
    h[0] = 0;
    for(i = 0; i < n; i++) rnk[sa[i]] = i;
    for(i = 0, j = 0; i < n; i ++) {
        j = j == 0? 0 : (j - 1);
        if(rnk[i] != 0) {
            while(i + j < n && sa[rnk[i] - 1] + j < n && str[i + j] == str[sa[rnk[i] - 1] + j]) j ++;
        }
        h[rnk[i]] = j;
    }
}
#define N 1000007
char str[N];
int data[N], num0[N], num9[N];
int sa[N], rnk[N], h[N];
bool c[N];
int getans() {
    int i, j, len = strlen(str), sum, cnt = 0, res = 0, ans = 0, p, a, b;
    memset(c, false, sizeof(c));
    for(i = 0; i < len; i ++) {
        if(h[i] < cnt) {
            cnt = h[i];
        } else {
            sum = data[cnt] + data[sa[i] + cnt] + c[cnt];
            while(sum % 10 == 0 && sa[i] + cnt < len) {
                cnt ++;
                c[cnt] = sum / 10;
                sum = data[cnt] + data[sa[i] + cnt] + c[cnt];
            }
        }
        if(cnt >= sa[i]) {
            p = 2 * sa[i];
            res = sa[i] + (c[sa[i]]? num9[p]: num0[p]);
        } else if(cnt >= len - sa[i]) {
            p = len - sa[i];
            if((c[p] && len - sa[i] + num9[p] > sa[i]) || (!c[p] && len - sa[i] + num0[p] > sa[i])) {
                a = sa[i] - (len - sa[i]);
            } else a = c[p]? num9[p]: num0[p];
            res = len - sa[i] + a;
        } else res = cnt;
        if(sa[i]) ans = max(ans, res);
    }
    return ans;
}
int main() {
    //freopen("input.txt", "r", stdin);
    int i, len, cnt0, cnt9, ans;
    while(gets(str)) {
        len = strlen(str);
        reverse(str, str + len);
        for(i = 0; i < len; i ++) data[i] = (int) str[i];
        data[len] = 0;
        dc3(data, sa, len + 1, 256);
        for(i = 0; i < len; i ++) sa[i] = sa[i + 1];
        for(i = 0; i < len; i ++) data[i] = str[i] - '0';
        calcheight(data, sa, rnk, h, len);
        memset(num0, 0, sizeof(num0));
        memset(num9, 0, sizeof(num9));
        cnt0 = 0, cnt9 = 0;
        for(i = len - 1; i >= 0; i --) {
            if(data[i] == 0) {
                cnt0 ++;
            } else cnt0 = 0;
            if(data[i] == 9) {
                cnt9 ++;
            } else cnt9 = 0;
            num0[i] = cnt0;
            num9[i] = cnt9;
        }
        printf("%d\n", getans());
    }
    return 0;
}//用dc3算法构建后缀数组，然后比对后缀和前缀