Mai intai trebuie sa te autentifici.
Cod sursa(job #2975938)
Utilizator | Data | 7 februarie 2023 21:13:36 | |
---|---|---|---|
Problema | PScPld | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva de probleme | Marime | 1.01 kb |
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("popcnt")
using namespace std;
ifstream fin ("pscpld.in");
ofstream fout ("pscpld.out");
const int MAX_N = 2'000'002;
int n, lft, rgt;
int pal[MAX_N + 5];
string input, s;
int main (){
ios_base::sync_with_stdio(false);
fin.tie(nullptr), fout.tie(nullptr);
fin>>input;
s += "(";
for(char c : input){
s += "*";
s += c;
}
s += "*)";
n = (int)s.size()-2;
lft = rgt = 0;
for(int i=1; i<=n; i++){
if(i <= rgt)
pal[i] = min(rgt - i, pal[lft + (rgt - i)]);
while(s[i - (pal[i]+1)] == s[i + (pal[i]+1)])
pal[i]++;
if(i + pal[i] > rgt){
lft = i - pal[i];
rgt = i + pal[i];
}
}
long long sol = 0;
for(int i=1; i<=n; i++)
if(s[i] == '*')
sol += (pal[i]+1) / 2;
else
sol += ((pal[i]+1) + 1) / 2;
fout<<sol;
return 0;
}