Pagini recente » Cod sursa (job #193053) | Rating Cismaru Mihai Claudiu (cizuss) | Xmoto | Diferente pentru utilizator/dornescuvlad intre reviziile 96 si 102 | Cod sursa (job #637464)
Cod sursa(job #637464)
#include <algorithm>
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
int lung[2000010];
int main()
{
ifstream cin("pscpld.in");
ofstream cout("pscpld.out");
string str;
cin >> str;
if (str[str.size() - 1] == '\n')
for (; ; );
str = " " + str;
int maxGs = 0, mij = 0, sol = 0;
for (int i = 1; i < str.size(); i++)
{
int x, y, loc;
if (maxGs < i)
mij = i, lung[2 * i - 1] = 1;
loc = 2 * i - 1;
lung[loc] = lung[mij - (loc - mij)];
x = i - lung[loc] / 2 - 1, y = i + lung[loc] / 2 + 1;
for (; x > 0 && y < str.size(); lung[loc] += 2, x--, y++)
if (str[x] != str[y])
break;
sol += (lung[loc] + 1) / 2;
if (maxGs < y - 1)
maxGs = y - 1, mij = loc;
loc = 2 * i;
lung[loc] = lung[mij - (loc - mij)];
x = i - lung[loc] / 2, y = i + lung[loc] / 2 + 1;
for (; x > 0 && y < str.size(); lung[loc] += 2, x--, y++)
if (str[x] != str[y])
break;
sol += lung[loc] / 2;
if (maxGs < y - 1)
maxGs = y - 1, mij = loc;
}
cout << sol;
return 0;
}