Pagini recente » Cod sursa (job #1829988) | Cod sursa (job #1063103) | Cod sursa (job #2850629) | Cod sursa (job #1801859) | Cod sursa (job #712556)
Cod sursa(job #712556)
#include <fstream>
#include <string>
using namespace std;
ifstream in("pscpld.in");
ofstream out("pscpld.out");
const int N = 2000005;
int n;
string s;
int v[N];
void read()
{
string auxStr;
in >> auxStr;
s += 'O';
for (int i = 0; i < (int)auxStr.size(); ++i) {
s += auxStr[i];
s += 'O';
}
n = s.size();
}
void solve()
{
int bestEnd = -1;
int bestCenter = 0;
for (int i = 0; i < n; ++i)
if (bestEnd <= i) {
int j;
for (j = 0; i+j < n && i-j >= 0 && s[i+j] == s[i-j]; ++j);
v[i] = j;
if (i + j - 1 > bestEnd) {
bestEnd = i + j - 1;
bestCenter = i;
}
}
else {
int opElement = bestCenter - (i - bestCenter);
if (i + v[opElement] - 1 < bestEnd)
v[i] = v[opElement];
else {
int j;
for (j = bestEnd - i; i+j < n && i-j >= 0 && s[i+j] == s[i-j]; ++j);
v[i] = j;
if (i + j - 1 > bestEnd) {
bestEnd = i + j - 1;
bestCenter = i;
}
}
}
}
int getAnswer()
{
int res = 0;
for (int i = 0; i < n; ++i) {
res += v[i]/2;
}
return res;
}
int main()
{
read();
solve();
out << getAnswer() << "\n";
return 0;
}