Pagini recente » Borderou de evaluare (job #155753) | Rezultatele filtrării | Cod sursa (job #2284080)
#include <cstdio>
#include <fstream>
#include <string>
#include <vector>
#define pb push_back
#define MIN(a, b) (((a) > (b)) ? (b) : (a))
const int VM(2000005) ;
std::ifstream in("pscpld.in");
std::ofstream out("pscpld.out");
std::string ch ;
std::vector<char> v ;
long long L[VM] ;
long long GetPal() {
register long long i ;
long long 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 ;
}
}
long long ans(0) ;
for (i = 0 ; i < v.size() ; ++ i) {
ans += (L[i] - 1) / 2 ;
}
return ans ;
}
int main(){
register long long i ;
in >> ch ;
long long n = ch.size() ;
for (i = 0 ; i < n ; ++ i) {
v.pb('*') ;
v.pb(ch[i]) ;
}
v.pb('*') ;
long long answer = GetPal() + n ;
out << answer ;
return 0;
}