Pagini recente » Cod sursa (job #303239) | Cod sursa (job #2382917) | Cod sursa (job #2162719) | Cod sursa (job #3040400) | Cod sursa (job #1584451)
#include <fstream>
using namespace std;
string s;
int n;
int p[2][1000005];
void Manacher()
{
int l = 0,r = -1;
for (int t = 0; t < 2; t++) // 0 = even length 1 = odd length
for (int i = 0; i < n; i++)
{
p[t][i] = i > r ? (1-!t) : min(p[t][l+r-i+!t],r-i+1);
int L = i - !t - p[t][i] + 1, R = i + p[t][i] - 1;
while (L-1 >= 0 && R+1 < n && s[L-1] == s[R+1]) ++R,--L,++p[t][i];
if (R > r)
l = L,r = R;
}
}
int main()
{
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
fin >> s;
n = s.size();
Manacher();
long long ret = 0;
for (int i = 0; i < n; i++)
ret += p[1][i] + p[0][i];
fout << ret << "\n";
}