Pagini recente » Cod sursa (job #812268) | Cod sursa (job #2749063) | Cod sursa (job #1821098) | Cod sursa (job #1493945) | Cod sursa (job #2415852)
#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 = s2 + s[i], s2 = s2 + '$';
s2 = s2 + '#';
int center = 0, right = 0, mirror = 0;
for(int i = 1; i + 1 < s2.size(); ++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;
}