Pagini recente » Cod sursa (job #2220222) | Cod sursa (job #592324) | Cod sursa (job #2835084) | Cod sursa (job #789951) | Cod sursa (job #973257)
Cod sursa(job #973257)
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin ("pscpld.in");
ofstream fout ("pscpld.out");
const int Nmax = 1000005;
int N; char S[Nmax]; int Sol[2 * Nmax]; int X[2 * Nmax];
void Read() {
fin >> S + 1;
N = strlen(S + 1);
for(int i = 1; S[i]; ++i)
X[2 * i] = S[i] - 'a' + 1;
N += N + 1; X[0] = -1; X[N + 1] = -2;
}
void Solve() {
int Center = -10000; int Right = -10000;
for(int i = 1; i <= N; ++i) {
int St = i, Dr = i;
if(i > Right)
Sol[i] = 0;
else {
int Radius = Right - Center;
Sol[i] = Sol[Center - Radius];
if(Sol[i] + i > Right)
Sol[i] = Right - i;
St = St - Sol[i]; Dr += Sol[i];
}
while(X[St - 1] == X[Dr + 1])
St--, ++Dr, ++Sol[i];
if(Dr > Right)
Right = Dr, Center = i;
}
}
int main() {
Read();
Solve();
long long Solution = 0;
for(int i = 1; i <= N; ++i)
Solution += (Sol[i] + 1) / 2;
fout << Solution <<'\n';
return 0;
}