Pagini recente » Cod sursa (job #2787141) | Cod sursa (job #1690888) | Cod sursa (job #2891283) | Cod sursa (job #1907758) | Cod sursa (job #2260563)
#include <fstream>
#include <vector>
#include <string.h>
using namespace std;
ifstream in("pscpld.in");
ofstream out("pscpld.out");
vector<char> v;
char ch[1000001];
long long cnt[2000001];
long long n, l, r, k;
long long ans;
int main()
{
in >> ch;
n = strlen(ch);
for(int i = 0; i < n; i++)
{
v.push_back('*');
v.push_back(ch[i]);
}
v.push_back('*');
for(int i = 0; i < (int)v.size(); i++)
{
if(i > r)
k = 0;
else
k = min(cnt[l+r-i], r-i);
while(i + k < (int)v.size() && i - k >= 0 && v[i + k] == v[i - k])
k++;
cnt[i] = k--;
if(i + k > r)
{
r = i + k;
l = i - k;
}
}
ans = n;
for(int i = 0; i < (int)v.size(); i++)
ans += (cnt[i] - 1) / 2;
out << ans;
return 0;
}