Pagini recente » Cod sursa (job #1531502) | Cod sursa (job #2574366) | Cod sursa (job #2320564) | Cod sursa (job #764475) | Cod sursa (job #3150683)
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")
#include <bits/stdc++.h>
using namespace std;
string s, t;
char c;
int pal[2000005], n, st, dr, sol, start, maxi, le, ri;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
int32_t main(int argc, char * argv[])
{
fin >> t;
for(int i = 0; t[i]; ++i)
{
s.push_back('#');
s.push_back(t[i]);
}
s.push_back('#');
n = s.length() - 1;
for(int i = 0; i <= n; ++i)
{
if(i < dr)
{
pal[i] = min(dr - i, pal[st + dr - i]);
}
while(i - pal[i] >= 0 && i + pal[i] <= n && s[i - pal[i]] == s[i + pal[i]])
{
pal[i]++;
}
if(i + pal[i] - 1 > dr)
{
dr = i + pal[i] - 1;
st = i - pal[i] + 1;
}
if(maxi < pal[i])
{
maxi = pal[i];
start = (i - pal[i] + 1) / 2; // maxi - 1 lungimea celui mai lung si end va fi start + maxi - 2
}
}
for(int i = 0; i <= n; ++i)
{
sol += pal[i] / 2;
}
fout << sol;
return 0;
}