Pagini recente » Cod sursa (job #330535) | Cod sursa (job #56296) | Cod sursa (job #2254021) | Cod sursa (job #1887994) | Cod sursa (job #2723146)
#include <fstream>
#include <string>
using namespace std;
ifstream fin ("pscpld.in");
ofstream fout ("pscpld.out");
string buff, s;
int pal[2000005];
int main()
{
int n, i, j, st, dr;
long long rasp;
fin >> buff;
s.push_back('#');
for (i = 0; i<buff.size(); i++)
{
s.push_back(buff[i]);
s.push_back('#');
}
n = s.size();
st = dr = -1;
for (i = 0; i<n; i++)
{
if (i <= dr)
j = min(pal[st + dr - i], dr - i + 1);
else
j = 1;
while (0 <= i - j && i + j < n && s[i-j] == s[i+j])
j++;
pal[i] = j;
if (i + j - 1 > dr)
{
dr = i + j - 1;
st = i - j + 1;
}
}
rasp = 0;
for (i = 0; i<n; i++)
rasp = rasp + pal[i];
fout << rasp/2;
return 0;
}