Pagini recente » Cod sursa (job #1834746) | Cod sursa (job #287976) | Cod sursa (job #3041259) | Cod sursa (job #2849134) | Cod sursa (job #2415858)
#include<bits/stdc++.h>
using namespace std;
ifstream f("pscpld.in");
ofstream g("pscpld.out");
string s, s2;
long long ans;
int dp[2000002], n;
int main()
{
f >> s;
n = s.size();
string s2 = "#$";
for(int i = 0; i < s.size(); ++i)
s2 += s[i], s2 += '$';
s2 += '#';
int center = 0, right = 0, mirror = 0;
for(int i = 1; i < s2.size() - 1; ++i)
{
mirror = 2 * center - i;
if(i < right)
dp[i] = min(dp[mirror], right - i);
while(dp[i] < n && s2[i - dp[i] - 1] == s2[i + dp[i] + 1])
++dp[i];
if(i + dp[i] > right)
center = i, right = i + dp[i];
ans = ans + dp[i] / 2 + dp[i] % 2;
}
g << ans << '\n';
return 0;
}