Pagini recente » Cod sursa (job #757940) | Autentificare | Cod sursa (job #160967) | Cod sursa (job #1298066) | Cod sursa (job #2247307)
/*#include <bits/stdc++.h>
using namespace std;
ifstream f("pscpld.in");
ofstream g("pscpld.out");
char s[1000001];
int main()
{//char ;
int nr,i,k,j,ok;
f>>s;
nr=strlen(s);
k=2;
while(k<strlen(s)-2+-)
{
for(i=0;i<strlen(s)-k+1;i++){ok=1;
if(k%2==0)
{for(j=i;j<=i+k-1;j++)if(s[j]!=s[i+k-j+1])ok=0;
if(ok==1)nr++;}
else {for(j=i;j<=i+k-1;j++)if(s[j]!=s[i+k-j+1]||s[(i+k+1)/2]!=s[(i+k+1)/2])ok=0;
if(ok==1)nr++;}
}k++;}
g<<nr;
f.close();
g.close();
return 0;
}
*/
#include <fstream>
//#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false), cin.tie(0);
ifstream cin("pscpld.in");
ofstream cout("pscpld.out");
const int N = 2e6 + 7;
string a;
string b;
int LPS[N];
void Manacher()
{
for(int i = 0; i < a.size(); i++)
b.push_back('#'), b.push_back(a[i]);
b.push_back('#');
int l = 0, r = -1;
for(int i = 0; i < b.size(); i++)
{
int k = (i > r ? 0 : min (LPS[l + r - i], r - i));
while(i + k < b.size() && i - k >= 0 && b[i + k] == b[i - k])
k++;
LPS[i] = k--;
if(i + k > r)
l = i - k, r = i + k;
}
}
main()
{
cin >> a;
Manacher();
long long ans = a.size() * 1LL;
for(int i = 0; i < b. size(); i++)
ans += (LPS[i] - 1) / 2LL;
cout << ans;
}