Pagini recente » Clasament 89726 | Cod sursa (job #1683974) | Romanii medaliati la IOI | Cod sursa (job #68064) | Cod sursa (job #1344494)
#include <fstream>
#include <string>
using namespace std;
ifstream fin ("pscpld.in");
ofstream fout ("pscpld.out");
int V[2000010];
string A, S;
int main()
{
fin >> A;
S += "@";
for (int i = 0; i < A.size(); i++)
{
S += "+";
S += A[i];
}
S += "+@";
int r = 0, c = 0;
for (int i = 1; i < S.size() - 1; i++)
{
if (i < r)
{
V[i] = min(r - i, V[c * 2 - i]);
}
while (i - V[i] - 1 > 0 &&
i + V[i] + 1 < S.size() &&
S[i - V[i] - 1] == S[i + V[i] + 1]) V[i] += 1;
if (r < V[i] + i)
{
r = V[i] + i;
c = i;
}
}
long long nr = 0;
for (int i = 1; i < S.size(); i++)
{
nr += (V[i] + 1) / 2;
}
fout << nr << '\n';
fout.close();
return 0;
}