Cod sursa(job #2247307)

Utilizator Codrincristea21Cristea Codrin Codrincristea21 Data 28 septembrie 2018 12:39:07
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
/*#include <bits/stdc++.h>

using namespace std;
ifstream f("pscpld.in");
ofstream g("pscpld.out");
char s[1000001];
int main()
{//char ;
int nr,i,k,j,ok;
f>>s;
nr=strlen(s);
k=2;
while(k<strlen(s)-2+-)
{
    for(i=0;i<strlen(s)-k+1;i++){ok=1;
    if(k%2==0)
            {for(j=i;j<=i+k-1;j++)if(s[j]!=s[i+k-j+1])ok=0;
                if(ok==1)nr++;}
    else {for(j=i;j<=i+k-1;j++)if(s[j]!=s[i+k-j+1]||s[(i+k+1)/2]!=s[(i+k+1)/2])ok=0;
                if(ok==1)nr++;}
}k++;}
g<<nr;
f.close();
g.close();

    return 0;
}
*/
#include <fstream>
//#include <bits/stdc++.h>

using namespace std;

#define IOS ios::sync_with_stdio(false), cin.tie(0);

ifstream cin("pscpld.in");
ofstream cout("pscpld.out");

const int N = 2e6 + 7;

string a;
string b;

int LPS[N];

void Manacher()
{
    for(int i = 0; i < a.size(); i++)
        b.push_back('#'), b.push_back(a[i]);
    b.push_back('#');

    int l = 0, r = -1;
    for(int i = 0; i < b.size(); i++)
    {
        int k = (i > r ? 0 : min (LPS[l + r - i], r - i));
        while(i + k < b.size() && i - k >= 0 && b[i + k] == b[i - k])
            k++;
        LPS[i] = k--;
        if(i + k > r)
            l = i - k,  r = i + k;
    }
}

main()
{
    cin >> a;
    Manacher();
    long long ans = a.size() * 1LL;
    for(int i = 0; i < b. size(); i++)
        ans += (LPS[i] - 1) / 2LL;
    cout << ans;
}