Pagini recente » Cod sursa (job #2446600) | Cod sursa (job #2456172) | Cod sursa (job #1449208) | Cod sursa (job #150829) | Cod sursa (job #2437617)
#include <fstream>
using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
const int NMax = 1e6;
int DP[NMax + 5], C, R, A[NMax + 5], N;
char S[NMax + 5]; long long Sol;
int Expandi(int c, int r)
{
while(c + r + 1 <= N && c - r - 1 && A[c + r + 1] == A[c - r - 1])
r++;
return r;
}
int Expandp(int c, int r)
{
while(c + r + 2 <= N && c - r - 1 && A[c + r + 2] == A[c - r - 1])
r++;
return r;
}
int main()
{
fin >> S;
for(int i = 0; S[i]; i++)
A[++N] = S[i] - 'a';
for(int i = 1; i <= N; i++)
{
if(i <= C + R) DP[i] = DP[C - i];
DP[i] = Expandi(i, DP[i]);
Sol += DP[i] + 1;
if(i + DP[i] > C + R)
C = i, R = DP[i];
}
C = R = 0;
for(int i = 1; i < N; i++)
{
DP[i] = 0;
if(A[i] != A[i + 1]) continue;
if(i <= C + R) DP[i] = DP[C - i + 1];
DP[i] = Expandp(i, DP[i]);
Sol += DP[i] + 1;
if(i + DP[i] > C + R)
C = i, R = DP[i];
}
fout << Sol << '\n';
fin.close();
fout.close();
return 0;
}