Pagini recente » Cod sursa (job #3155386) | Cod sursa (job #3148894) | Cod sursa (job #367105) | Cod sursa (job #2284069)
#include <cstdio>
#include <cstring>
#include <vector>
#define pb push_back
#define MIN(a, b) (((a) > (b)) ? (b) : (a))
const int VM(1000000) ;
char ch[VM] ;
std::vector<char> v ;
std::vector<int> L(VM) ;
int GetPal() {
register int i ;
int left(0), right(0), pos(0) ;
for (i = 0 ; i < v.size() ; ++ i) {
if(i > right)
pos = 0 ;
else
pos = MIN(L[right + left - i], right - i) ;
while (i + pos < v.size() && i - pos >= 0 && v[i - pos] == v[i + pos])
++ pos ;
L[i] = pos -- ;
if (i + pos > right) {
right = i + pos ;
left = i - pos ;
}
}
int ans(0) ;
for (i = 0 ; i < L.size() ; ++ i) {
ans += (L[i] - 1) / 2 ;
}
return ans ;
}
int main()
{
freopen("pscpld.in", "r", stdin) ;
freopen("pscpld.out", "w", stdout) ;
register int i ;
gets(ch) ;
int n = strlen(ch) ;
for (i = 0 ; i < n ; ++ i) {
v.pb('|') ;
v.pb(ch[i]) ;
}
v.pb('|') ;
int answer = GetPal() + n ;
printf("%d", answer) ;
return 0;
}