Pagini recente » Cod sursa (job #2969428) | Cod sursa (job #1789005) | Cod sursa (job #871799) | Cod sursa (job #1137246) | Cod sursa (job #2785497)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
string s;
int n;
int dp[2000005];
void manacher()
{
if (n < 2){
dp[1] = 1;
return;
}
string s2 = "#";
for (int i=0;i<n;i++){
s2.push_back(s[i]);
s2.push_back('#');
}
int cx = 0, mx = 0;
const int n2 = 2 * n + 1;
for (int i=1;i<n2;i++){
int j = 0;
if (i >= mx){
j = i + 1;
}else{
int ii = 2 * cx - i;
dp[i] = min(mx - i, dp[ii]);
if (ii - dp[ii] <= cx - dp[cx]){
j = mx + 1;
}
}
while(j && (j < n2) && (2 * i - j >= 0) && (s2[j] == s2[2*i-j]))
dp[i] ++, j ++;
if (i + dp[i] > mx)
mx = i + dp[i], cx = i;
}
/*for (int i=0;i<n2;i++)
fout << dp[i] << ' ';
fout << '\n';
for (int i=0;i<n2;i++)
fout << s2[i] << ' ';
fout << '\n';*/
long long suma = 0;
for (int i=0;i<n2;i++){
suma += (dp[i] + 1) / 2;
}
fout << suma << '\n';
}
int main() {
getline(fin, s);
n = s.size();
manacher();
return 0;
}