Pagini recente » Cod sursa (job #652945) | Cod sursa (job #2030950) | Cod sursa (job #2351943) | Cod sursa (job #1610345) | Cod sursa (job #2377067)
//#include "pch.h"
#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>
using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
long long dp[2000005];
string aux;
string s;
int main() {
ios::sync_with_stdio(false);
fin.tie(0); fout.tie(0);
long long ans = 0;
fin >> aux;
s += '$';
for (int i = 0; i < aux.size(); ++i) {
s += '#';
s += aux[i];
}
s += '#';
s += '@';
int n = s.size();
int c = 0, r = 0;
for (int i = 2; i < n; ++i) {
int mirror = 2 * c - i;
if (i < r) {
dp[i] = min(1LL*r - i, dp[mirror]);
}
while (s[i + dp[i] + 1] == s[i - dp[i] - 1] && dp[i] < n ) {
dp[i]++;
}
ans += dp[i] / 2 + (dp[i] % 2);
if (dp[i] + i > r) {
c = i;
r = dp[i] + i;
}
}
/*cout << s << '\n';
for (int i = 0; i < n; ++i) {
cout << dp[i];
}*/
//fout << '\n';
fout << ans << '\n';
}