Cod sursa(job #2596901)
Utilizator | Data | 10 aprilie 2020 16:54:48 | |
---|---|---|---|
Problema | PScPld | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva de probleme | Marime | 0.41 kb |
#include <bits/stdc++.h>
using namespace std;
ifstream in("pscpld.in");
ofstream out("pscpld.out");
string s;
long long a[2000002];
int main(){
long long n,i,j,c=1,p=2,S=1;
in>>s;
n=s.size()*2+1;
a[1]=1;
for(i=2;i<n;i++){
j=min(a[c*2-i],max(p-i,0LL));
for(;i+j<n&&j<i&&((i+j)%2||s[(i+j+1)/2]==s[(i-j-1)/2]);j++);
if(i+j>p)
c=i,p=i+j;
a[i]=j;
S+=j/2+j%2;
}
out<<S;
return 0;
}