Pagini recente » Cod sursa (job #530087) | Diferente pentru autumn-warmup-2007/solutii/runda-2 intre reviziile 56 si 42 | Cod sursa (job #1181773) | Cod sursa (job #1763419) | 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;
}