Pagini recente » Cod sursa (job #3145089) | Cod sursa (job #2824066) | Cod sursa (job #1074743) | Cod sursa (job #1497270) | Cod sursa (job #1221921)
#include<cstdio>
#include<fstream>
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<bitset>
#include<deque>
#include<queue>
#include<set>
#include<map>
#include<cmath>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<unordered_map>
#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>
using namespace std;
const int nmax = 100005;
int i, n, C, R, mirror, l, r, p[2 * nmax];
ll sol;
string s, t;
int main()
{
cin.sync_with_stdio(false);
freopen("pscpld.in", "r", stdin);
freopen("pscpld.out", "w", stdout);
cin >> s;
t += '#';
for(i = 0; i < s.size(); i++)
{
n++;
t += s[i];
p[n] = 1;
t += '$';
n++;
}
for(i = 1; i < n; i++)
{
mirror = 2 * C - i;
if(i <= R)
p[i] = min(p[mirror], R - i + 1);
l = i - p[i] + 1;
r = i + p[i] - 1;
while(l - 2 >= 1 && r + 2 <= n && t[l - 2] == t[r + 2])
{
l -= 2;
r += 2;
p[i] += 2;
}
if(r > R)
{
R = r;
C = i;
}
sol += (p[i] + 1) / 2;
}
cout << sol << '\n';
return 0;
}