Pagini recente » Cod sursa (job #1587364) | Cod sursa (job #848892) | Profil M@2Te4i | Cod sursa (job #1292848) | Cod sursa (job #1967550)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
const int MAX_N = 1e6 + 2;
char aux[MAX_N], s[2 * MAX_N];
int n, dp[MAX_N];
void Konstruieste()
{
int m = 0;
for (int i = 1; i <= n; ++i)
{
s[++m] = '#';
s[++m] = aux[i];
}
s[++m] = '#';
n = m;
}
void Manaker()
{
long long ans = 0;
int c = 0;
for (int i = 2; i <= n; ++i)
{
dp[i] = 1;
if(c + dp[c] > i) {
dp[i] = min(c + dp[c] - i, dp[2 * c - i]);
}
dp[i] = max(1, dp[i]);
while (i - dp[i] > 0 && i + dp[i] <= n && s[i - dp[i]] == s[i + dp[i]])
++dp[i];
if (i % 2 == 0)
{
ans += (dp[i]) / 2;
}
else ans += (dp[i] - 1) / 2;
if(i + dp[i] > c + dp[c])
c = i;
}
fout << ans;
}
int main()
{
fin >> (aux + 1);
n = strlen(aux + 1);
Konstruieste();
Manaker();
}