Pagini recente » Cod sursa (job #2730887) | Cod sursa (job #225803) | Cod sursa (job #225278) | Cod sursa (job #2806998) | Cod sursa (job #2437647)
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
const int NMax = 1e6;
int DP[NMax + 5], C, R, N;
char A[NMax + 5]; long long Sol;
int Expand(int l, int r)
{
int Ans = 0;
while(l <= N && r && A[l] == A[r])
Ans++, l--, r++;
return Ans;
}
int main()
{
fin.getline(A + 1, NMax + 5);
N = strlen(A + 1);
for(int i = 1; i <= N; i++)
{
if(i <= R) DP[i] = min(DP[C - (i - C)], R - i);
DP[i] += Expand(i - DP[i] - 1, i + DP[i] + 1);
Sol += DP[i] + 1;
if(i + DP[i] > R)
C = i, R = DP[i] + i;
}
C = R = 0;
for(int i = 1; i <= N; i++)
DP[i] = 0;
for(int i = 1; i < N; i++)
{
DP[i] = 0;
if(A[i] != A[i + 1]) continue;
if(i <= R) DP[i] = min(DP[C - (i - C + 1)], R - i - 1);
DP[i] += Expand(i - DP[i] - 1, i + DP[i] + 2);
Sol += DP[i] + 1;
if(i + DP[i] + 1 > R)
C = i, R = DP[i] + i + 1;
}
fout << Sol << '\n';
fin.close();
fout.close();
return 0;
}