Mai intai trebuie sa te autentifici.
Cod sursa(job #3040105)
Utilizator | Data | 29 martie 2023 12:32:42 | |
---|---|---|---|
Problema | PScPld | Scor | 30 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva de probleme | Marime | 0.78 kb |
#include <bits/stdc++.h>
using namespace std;
string s, a;
int ans[2000001], st, dr, mij, sum;
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
int main()
{
fin >> a;
s += '!';
for(int i = 0; i < a.size(); ++ i)
{
s += a[i];
s += '!';
}
st = -1;
dr = -1 ;
for(int i = 0; i < s.size(); ++ i)
{
if(i <= dr)
{
ans[i] = min(dr - i, ans[st + dr - i]);
}
while(i - ans[i] >= 0 && s[i - ans[i]] == s[i + ans[i]])
{
ans[i]++;
}
if(i + ans[i]> dr)
{
dr = i + ans[i];
st = i - ans[i];
}
}
for(int i = 0; i < s.size(); i ++)
sum += ans[i] / 2;
fout << sum;
return 0;
}