Pagini recente » Cod sursa (job #1424145) | Cod sursa (job #1189949) | Cod sursa (job #1581492) | Cod sursa (job #998575) | Cod sursa (job #932371)
Cod sursa(job #932371)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <deque>
using namespace std;
ifstream f("pscpld.in");
ofstream g("pscpld.out");
#define nmax 1000005
#define ll long long
string A, S;
int z[nmax*2];
void citeste(){
getline(f, A);
for(int i=0; i<A.size()-1; ++i){
S += A[i]; S += '*';
}
S += A[A.size()-1];
}
inline int extinde(int st, int dr){
int cnt = 0;
for(int i=st, j=dr; i>=0 && j<S.size(); --i, ++j){
if (S[i] != S[j]) return cnt;
++cnt;
}
return cnt;
}
void bagaZvalues(){
z[0] = 0; int centru = -1; int dr = -1;
for(int i=1; i<S.size(); ++i){
if (dr < i){
z[i] = extinde(i-1, i+1);
if (z[i] != 0){
centru = i; dr = i + z[i];
}
continue;
}else{
int i2 = centru - (i-centru);// simetricul lui i in raport cu centru
int lungBeta = dr - i; // fac abstractie de punctul i
if (z[i2] < lungBeta){
z[i] = z[i2]; continue;
}
z[i] = lungBeta + extinde(i - lungBeta -1 , i + lungBeta + 1);
if (i + z[i] > dr){
centru = i; dr = i + z[i];
}
}
}
}
void rezolva(){
// z[i] = cat de mult ma pot duce in stanga si in dreapta evident
bagaZvalues();
// le numar
ll cnt = 0LL;
for(int i=0; i<S.size(); ++i){
if (S[i] == '*'){
cnt += (ll)(z[i] / 2 + (z[i] % 2));
}else {
cnt += (ll)(z[i] / 2 + 1);// +1 pt ca il iau doar pe el (pe i);
}
}
g << cnt << "\n";
}
int main(){
citeste();
rezolva();
f.close();
g.close();
return 0;
}