Pagini recente » Cod sursa (job #694673) | Cod sursa (job #461162) | Cod sursa (job #9448) | Cod sursa (job #2632539) | Cod sursa (job #3275883)
#include <fstream>
using namespace std;
ifstream in("pscpld.in");
ofstream out("pscpld.out");
int n, ans;
string init, s;
int man[2000005];
int main()
{
in>>init;
for(auto it: init)
{
s += string("#") + it;
}
s += string("#");
n = s.size();
s = '$' + s + '^';
int l = 1;
int r = 1;
for(int i = 1; i<=n; i++)
{
man[i] = max(0, min(r - i, man[l + (r - i)]));
while(s[i - man[i]] == s[i + man[i]])
{
man[i]++;
}
if(i + man[i] > r)
{
l = i - man[i];
r = i + man[i];
}
if(i != 1 && i != n)
{
if(s[i] == '#')
{
ans += (man[i] - 1) / 2;
}
else
{
ans += man[i] / 2;
}
}
}
/*for(int i = 1; i<=n; i++)
{
out<<s[i]<<" ";
}
out<<'\n';
for(int i = 1; i<=n; i++)
{
out<<man[i]<<" ";
}
out<<'\n';*/
out<<ans;
return 0;
}