Pagini recente » Cod sursa (job #1167760) | Cod sursa (job #580862) | Cod sursa (job #1679471) | Cod sursa (job #1096424) | Cod sursa (job #641835)
Cod sursa(job #641835)
#include <cstring>
#include <fstream>
using namespace std;
int N, maxP[2][1000002];
long long result;
char A[1000004];
int main()
{
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
fin >> A;
N = strlen(A);
int pos1 = 0, pos2 = 0;
for (int i = 1; i <= N; ++i) // Calculez maxP[0][i] si maxP[1][i]
{
// maxP[0][i]
maxP[0][i] = 0;
if (pos1 + maxP[0][pos1] >= i)
maxP[0][i] = max(maxP[0][i], maxP[0][2 * pos1 - i]);
while (i - maxP[0][i] - 1 >= 1 && i + maxP[0][i] + 1 <= N && A[i - maxP[0][i] - 2] == A[i + maxP[0][i]])
++maxP[0][i];
if (i + maxP[0][i] > pos1 + maxP[0][pos1])
pos1 = i;
result += maxP[0][i] + 1;
// maxP[1][i]
maxP[1][i] = 0;
if (pos2 + maxP[1][pos2] >= i + 1)
maxP[1][i] = max(maxP[1][i], maxP[1][2 * pos2 - i]);
while (i - maxP[1][i] >= 1 && i + maxP[1][i] + 1 <= N && A[i - maxP[1][i] - 1] == A[i + maxP[1][i]])
++maxP[1][i];
if (i + maxP[1][i] > pos2 + maxP[1][pos2])
pos2 = i;
result += maxP[1][i];
}
fout << result;
fin.close();
fout.close();
}