Pagini recente » Cod sursa (job #2549344) | Cod sursa (job #278822) | Cod sursa (job #1323551) | Cod sursa (job #75980) | Cod sursa (job #3266367)
#include <fstream>
#include <vector>
using namespace std;
ifstream cin("pscpld.in");
ofstream cout("pscpld.out");
int main()
{
string s;
string cs;
cin >> s;
cs.append(1, '.');
for(int i = 0; i < s.size(); i++)
{
cs.append(1, s[i]);
cs.append(1, '.');
}
// for(int i = 0; i < cs.size(); i++)
// {
// cout << cs[i] << " ";
// }
// cout << "\n";
vector<int> man(cs.size());
int best = 0;
for(int i = 0; i < cs.size(); i++)
{
int l = 1;
if(best + man[best]/2 >= i)
{
l = min(man[2 * best - i]/2, best + man[best]/2 - i) * 2 + 1;
}
while(i + l/2 + 1 < cs.size() && i - l/2 - 1 >= 0 && cs[i + l/2 + 1] == cs[i - l/2 - 1])
{
l += 2;
}
man[i] = l;
if(i + l/2 > best + man[best]/2)
{
best = i;
}
// cout << man[i] << " ";
}
long long sum = 0;
for(int i = 0; i < cs.size(); i++)
{
sum += (man[i] / 2 + 1) / 2;
}
cout << sum;
}