## 【BZOJ 3790】神奇项链

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int MAXN = 120000;

char pat[MAXN],chr[MAXN];
int n,l[MAXN],r[MAXN],len[MAXN],ord[MAXN];

namespace FenwickTree{
#define BIT FenwickTree
#define low(x) (x&(-x))
#define INF 1000000000
int arr[MAXN],buf[MAXN];

inline void init(){
for (int i=1;i<=n;i++)
arr[i] = buf[i] = INF;
}

inline int query(int left, int right){
if (right < left) return INF; else { int ret = INF; while (right >= left){
if (right-low(right)+1>=left) ret = min(ret,arr[right]),right-=low(right);
else ret = min(ret,buf[right]), right--;
}
return ret;
}
}

inline void modify(int pos, int nv){
if (buf[pos] > nv) {
buf[pos] = nv;
for (int i=pos;i<=n;i+=low(i)) if (arr[i] > nv) arr[i] = nv;
else break;
} else return;
}
};

inline bool sort_cmp(const int &A, const int &B){
return r[A] < r[B];
}

inline int manacher(){
int m=n*2+1,itr=0;
for (int i=1;i<=n;i++)
chr[i*2-1] = '@',
chr[i*2] = pat[i];
chr[m] = '@'; chr[m+1] = '#'; chr[0] = '\$';

for (int i=1,p1,p2;i<=m;i++){ if (itr+len[itr] > i)  len[i] = min(len[2*itr-i],itr+len[itr]-i);
else len[i] = 0;
p1 = i-len[i]; p2 = i+len[i];
while (chr[--p1] == chr[++p2]) len[i]++;
if (itr+len[itr] < i+len[i]) itr = i;
}

for (int i=1;i<=m;i++)
r[i] = i+len[i],
l[i] = i-len[i],
ord[i] = i;
sort(ord+1,ord+m,sort_cmp);

n = m; BIT::init(); BIT::modify(1,0);
for (int j=1,i=ord[j],tmp;j<=n;j++,i=ord[j]){
tmp = BIT::query(l[i],r[i]-1)+1;
BIT::modify(r[i],tmp);
}

return BIT::query(m-1,m)-1;
}

int main(){
while (~scanf("%s",pat+1)){
n = strlen(pat+1);
printf("%dn",manacher());
}
return 0;
}