#include <iostream>
#include <string>
#include <algorithm> // std::min
using namespace std;
const int MAX_N = 5000;
int seg[2 * MAX_N];
int segsL[MAX_N][2 * MAX_N];
int m[MAX_N][MAX_N][2];
int dp[MAX_N][MAX_N];
int best;
// Adapted from https://c...content-available-to-author-only...s.com/blog/entry/18051
void update(int n, int p, int value) { // set value at position p
for (seg[p += n] = value; p > 1; p >>= 1)
seg[p >> 1] = seg[p] + seg[p ^ 1];
}
// Adapted from https://c...content-available-to-author-only...s.com/blog/entry/18051
int query(int n, int l, int r) { // sum on interval [l, r)
int res = 0;
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (l & 1) res += seg[l++];
if (r & 1) res += seg[--r];
}
return res;
}
// Adapted from https://c...content-available-to-author-only...s.com/blog/entry/18051
void updateL(int n, int i, int p, int value) { // set value at position p
for (segsL[i][p += n] = value; p > 1; p >>= 1)
segsL[i][p >> 1] = segsL[i][p] + segsL[i][p ^ 1];
}
// Adapted from https://c...content-available-to-author-only...s.com/blog/entry/18051
int queryL(int n, int i, int l, int r) { // sum on interval [l, r)
int res = 0;
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (l & 1) res += segsL[i][l++];
if (r & 1) res += segsL[i][--r];
}
return res;
}
void precalc(int n, string & s) {
int i, j;
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
// [longest match left, longest match right]
m[i][j][0] = (s[i] == s[j]) & 1;
m[i][j][1] = (s[i] == s[j]) & 1;
}
}
for (i = n - 2; i >= 0; i--)
for (j = n - 2; j >= 0; j--)
m[i][j][1] = s[i] == s[j] ? 1 + m[i + 1][j + 1][1] : 0;
for (i = 1; i < n; i++)
for (j = 1; j < n; j++)
m[i][j][0] = s[i] == s[j] ? 1 + m[i - 1][j - 1][0] : 0;
}
void f(int n, string & s) {
int i, j, k, longest;
dp[0][n - 1] = 1;
update(n, n - 1, 1);
updateL(n, n - 1, 0, 1);
// Right side initialisation
for (j = n - 2; j >= 0; j--) {
if (s[0] == s[j + 1]) {
longest = std::min(j + 1, m[0][j + 1][1]);
for (k = j + 1; k <= j + longest; k++)
dp[0][j] |= dp[0][k];
if (dp[0][j]) {
update(n, j, 1);
updateL(n, j, 0, 1);
best = std::min(best, j + 1);
}
}
}
// Left side initialisation
for (i = 1; i < n; i++) {
if (s[i - 1] == s[n - 1]) {
// We are bound by the current range
longest = std::min(n - i, m[i - 1][n - 1][0]);
for (k = i - 1; k >= i - longest; k--)
dp[i][n - 1] |= dp[k][n - 1];
if (dp[i][n - 1]) {
updateL(n, n - 1, i, 1);
best = std::min(best, n - i);
}
}
}
for (i = 1; i <= n - 2; i++) {
for (int ii = 0; ii < MAX_N; ii++) {
seg[ii * 2] = 0;
seg[ii * 2 + 1] = 0;
}
update(n, n - 1, dp[i][n - 1]);
for (j = n - 2; j >= i; j--) {
// We removed on the right
if (s[i] == s[j + 1]) {
// We are bound by half the current range
longest = std::min(j - i + 1, m[i][j + 1][1]);
//for (k=j+1; k<=j+longest; k++)
//dp[i][j] |= dp[i][k];
if (query(n, j + 1, j + longest + 1)) {
dp[i][j] = 1;
update(n, j, 1);
updateL(n, j, i, 1);
}
}
// We removed on the left
if (s[i - 1] == s[j]) {
// We are bound by half the current range
longest = std::min(j - i + 1, m[i - 1][j][0]);
//for (k=i-1; k>=i-longest; k--)
//dp[i][j] |= dp[k][j];
if (queryL(n, j, i - longest, i)) {
dp[i][j] = 1;
updateL(n, j, i, 1);
update(n, j, 1);
}
}
if (dp[i][j])
best = std::min(best, j - i + 1);
}
}
}
int main() {
string s;
cin >> s;
int n = s.length();
best = n;
precalc(n, s);
f(n, s);
cout << best;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8c3RyaW5nPgojaW5jbHVkZSA8YWxnb3JpdGhtPiAgICAvLyBzdGQ6Om1pbgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmNvbnN0IGludCBNQVhfTiA9IDUwMDA7CgppbnQgc2VnWzIgKiBNQVhfTl07CmludCBzZWdzTFtNQVhfTl1bMiAqIE1BWF9OXTsKaW50IG1bTUFYX05dW01BWF9OXVsyXTsKaW50IGRwW01BWF9OXVtNQVhfTl07CmludCBiZXN0OwoKLy8gQWRhcHRlZCBmcm9tIGh0dHBzOi8vYy4uLmNvbnRlbnQtYXZhaWxhYmxlLXRvLWF1dGhvci1vbmx5Li4ucy5jb20vYmxvZy9lbnRyeS8xODA1MQp2b2lkIHVwZGF0ZShpbnQgbiwgaW50IHAsIGludCB2YWx1ZSkgeyAvLyBzZXQgdmFsdWUgYXQgcG9zaXRpb24gcAogIGZvciAoc2VnW3AgKz0gbl0gPSB2YWx1ZTsgcCA+IDE7IHAgPj49IDEpCiAgICBzZWdbcCA+PiAxXSA9IHNlZ1twXSArIHNlZ1twIF4gMV07Cn0KLy8gQWRhcHRlZCBmcm9tIGh0dHBzOi8vYy4uLmNvbnRlbnQtYXZhaWxhYmxlLXRvLWF1dGhvci1vbmx5Li4ucy5jb20vYmxvZy9lbnRyeS8xODA1MQppbnQgcXVlcnkoaW50IG4sIGludCBsLCBpbnQgcikgeyAvLyBzdW0gb24gaW50ZXJ2YWwgW2wsIHIpCiAgaW50IHJlcyA9IDA7CiAgZm9yIChsICs9IG4sIHIgKz0gbjsgbCA8IHI7IGwgPj49IDEsIHIgPj49IDEpIHsKICAgIGlmIChsICYgMSkgcmVzICs9IHNlZ1tsKytdOwogICAgaWYgKHIgJiAxKSByZXMgKz0gc2VnWy0tcl07CiAgfQogIHJldHVybiByZXM7Cn0KLy8gQWRhcHRlZCBmcm9tIGh0dHBzOi8vYy4uLmNvbnRlbnQtYXZhaWxhYmxlLXRvLWF1dGhvci1vbmx5Li4ucy5jb20vYmxvZy9lbnRyeS8xODA1MQp2b2lkIHVwZGF0ZUwoaW50IG4sIGludCBpLCBpbnQgcCwgaW50IHZhbHVlKSB7IC8vIHNldCB2YWx1ZSBhdCBwb3NpdGlvbiBwCiAgZm9yIChzZWdzTFtpXVtwICs9IG5dID0gdmFsdWU7IHAgPiAxOyBwID4+PSAxKQogICAgc2Vnc0xbaV1bcCA+PiAxXSA9IHNlZ3NMW2ldW3BdICsgc2Vnc0xbaV1bcCBeIDFdOwp9Ci8vIEFkYXB0ZWQgZnJvbSBodHRwczovL2MuLi5jb250ZW50LWF2YWlsYWJsZS10by1hdXRob3Itb25seS4uLnMuY29tL2Jsb2cvZW50cnkvMTgwNTEKaW50IHF1ZXJ5TChpbnQgbiwgaW50IGksIGludCBsLCBpbnQgcikgeyAvLyBzdW0gb24gaW50ZXJ2YWwgW2wsIHIpCiAgaW50IHJlcyA9IDA7CiAgZm9yIChsICs9IG4sIHIgKz0gbjsgbCA8IHI7IGwgPj49IDEsIHIgPj49IDEpIHsKICAgIGlmIChsICYgMSkgcmVzICs9IHNlZ3NMW2ldW2wrK107CiAgICBpZiAociAmIDEpIHJlcyArPSBzZWdzTFtpXVstLXJdOwogIH0KICByZXR1cm4gcmVzOwp9Cgp2b2lkIHByZWNhbGMoaW50IG4sIHN0cmluZyAmIHMpIHsKICBpbnQgaSwgajsKICBmb3IgKGkgPSAwOyBpIDwgbjsgaSsrKSB7CiAgICBmb3IgKGogPSAwOyBqIDwgbjsgaisrKSB7CiAgICAgIC8vIFtsb25nZXN0IG1hdGNoIGxlZnQsIGxvbmdlc3QgbWF0Y2ggcmlnaHRdCiAgICAgIG1baV1bal1bMF0gPSAoc1tpXSA9PSBzW2pdKSAmIDE7CiAgICAgIG1baV1bal1bMV0gPSAoc1tpXSA9PSBzW2pdKSAmIDE7CiAgICB9CiAgfQoKICBmb3IgKGkgPSBuIC0gMjsgaSA+PSAwOyBpLS0pCiAgICBmb3IgKGogPSBuIC0gMjsgaiA+PSAwOyBqLS0pCiAgICAgIG1baV1bal1bMV0gPSBzW2ldID09IHNbal0gPyAxICsgbVtpICsgMV1baiArIDFdWzFdIDogMDsKCiAgZm9yIChpID0gMTsgaSA8IG47IGkrKykKICAgIGZvciAoaiA9IDE7IGogPCBuOyBqKyspCiAgICAgIG1baV1bal1bMF0gPSBzW2ldID09IHNbal0gPyAxICsgbVtpIC0gMV1baiAtIDFdWzBdIDogMDsKfQoKdm9pZCBmKGludCBuLCBzdHJpbmcgJiBzKSB7CiAgaW50IGksIGosIGssIGxvbmdlc3Q7CgogIGRwWzBdW24gLSAxXSA9IDE7CiAgdXBkYXRlKG4sIG4gLSAxLCAxKTsKICB1cGRhdGVMKG4sIG4gLSAxLCAwLCAxKTsKCiAgLy8gUmlnaHQgc2lkZSBpbml0aWFsaXNhdGlvbgogIGZvciAoaiA9IG4gLSAyOyBqID49IDA7IGotLSkgewogICAgaWYgKHNbMF0gPT0gc1tqICsgMV0pIHsKICAgICAgbG9uZ2VzdCA9IHN0ZDo6bWluKGogKyAxLCBtWzBdW2ogKyAxXVsxXSk7CiAgICAgIGZvciAoayA9IGogKyAxOyBrIDw9IGogKyBsb25nZXN0OyBrKyspCiAgICAgICAgZHBbMF1bal0gfD0gZHBbMF1ba107CiAgICAgIGlmIChkcFswXVtqXSkgewogICAgICAgIHVwZGF0ZShuLCBqLCAxKTsKICAgICAgICB1cGRhdGVMKG4sIGosIDAsIDEpOwogICAgICAgIGJlc3QgPSBzdGQ6Om1pbihiZXN0LCBqICsgMSk7CiAgICAgIH0KICAgIH0KICB9CgogIC8vIExlZnQgc2lkZSBpbml0aWFsaXNhdGlvbgogIGZvciAoaSA9IDE7IGkgPCBuOyBpKyspIHsKICAgIGlmIChzW2kgLSAxXSA9PSBzW24gLSAxXSkgewogICAgICAvLyBXZSBhcmUgYm91bmQgYnkgdGhlIGN1cnJlbnQgcmFuZ2UKICAgICAgbG9uZ2VzdCA9IHN0ZDo6bWluKG4gLSBpLCBtW2kgLSAxXVtuIC0gMV1bMF0pOwogICAgICBmb3IgKGsgPSBpIC0gMTsgayA+PSBpIC0gbG9uZ2VzdDsgay0tKQogICAgICAgIGRwW2ldW24gLSAxXSB8PSBkcFtrXVtuIC0gMV07CiAgICAgIGlmIChkcFtpXVtuIC0gMV0pIHsKICAgICAgICB1cGRhdGVMKG4sIG4gLSAxLCBpLCAxKTsKICAgICAgICBiZXN0ID0gc3RkOjptaW4oYmVzdCwgbiAtIGkpOwogICAgICB9CiAgICB9CiAgfQoKICBmb3IgKGkgPSAxOyBpIDw9IG4gLSAyOyBpKyspIHsKICAgIGZvciAoaW50IGlpID0gMDsgaWkgPCBNQVhfTjsgaWkrKykgewogICAgICBzZWdbaWkgKiAyXSA9IDA7CiAgICAgIHNlZ1tpaSAqIDIgKyAxXSA9IDA7CiAgICB9CiAgICB1cGRhdGUobiwgbiAtIDEsIGRwW2ldW24gLSAxXSk7CiAgICBmb3IgKGogPSBuIC0gMjsgaiA+PSBpOyBqLS0pIHsKICAgICAgLy8gV2UgcmVtb3ZlZCBvbiB0aGUgcmlnaHQKICAgICAgaWYgKHNbaV0gPT0gc1tqICsgMV0pIHsKICAgICAgICAvLyBXZSBhcmUgYm91bmQgYnkgaGFsZiB0aGUgY3VycmVudCByYW5nZQogICAgICAgIGxvbmdlc3QgPSBzdGQ6Om1pbihqIC0gaSArIDEsIG1baV1baiArIDFdWzFdKTsKICAgICAgICAvL2ZvciAoaz1qKzE7IGs8PWorbG9uZ2VzdDsgaysrKQogICAgICAgIC8vZHBbaV1bal0gfD0gZHBbaV1ba107CiAgICAgICAgaWYgKHF1ZXJ5KG4sIGogKyAxLCBqICsgbG9uZ2VzdCArIDEpKSB7CiAgICAgICAgICBkcFtpXVtqXSA9IDE7CiAgICAgICAgICB1cGRhdGUobiwgaiwgMSk7CiAgICAgICAgICB1cGRhdGVMKG4sIGosIGksIDEpOwogICAgICAgIH0KICAgICAgfQogICAgICAvLyBXZSByZW1vdmVkIG9uIHRoZSBsZWZ0CiAgICAgIGlmIChzW2kgLSAxXSA9PSBzW2pdKSB7CiAgICAgICAgLy8gV2UgYXJlIGJvdW5kIGJ5IGhhbGYgdGhlIGN1cnJlbnQgcmFuZ2UKICAgICAgICBsb25nZXN0ID0gc3RkOjptaW4oaiAtIGkgKyAxLCBtW2kgLSAxXVtqXVswXSk7CiAgICAgICAgLy9mb3IgKGs9aS0xOyBrPj1pLWxvbmdlc3Q7IGstLSkKICAgICAgICAvL2RwW2ldW2pdIHw9IGRwW2tdW2pdOwogICAgICAgIGlmIChxdWVyeUwobiwgaiwgaSAtIGxvbmdlc3QsIGkpKSB7CiAgICAgICAgICBkcFtpXVtqXSA9IDE7CiAgICAgICAgICB1cGRhdGVMKG4sIGosIGksIDEpOwogICAgICAgICAgdXBkYXRlKG4sIGosIDEpOwogICAgICAgIH0KICAgICAgfQogICAgICBpZiAoZHBbaV1bal0pCiAgICAgICAgYmVzdCA9IHN0ZDo6bWluKGJlc3QsIGogLSBpICsgMSk7CiAgICB9CiAgfQp9CgppbnQgbWFpbigpIHsKICBzdHJpbmcgczsKICBjaW4gPj4gczsKICBpbnQgbiA9IHMubGVuZ3RoKCk7CiAgYmVzdCA9IG47CiAgcHJlY2FsYyhuLCBzKTsKICBmKG4sIHMpOwoKICBjb3V0IDw8IGJlc3Q7Cn0=