Pagini recente » Cod sursa (job #3317719) | Cod sursa (job #3332553) | Cod sursa (job #3310710) | Cod sursa (job #3320436) | Cod sursa (job #3349961)
#include <iostream>
#include <fstream>
#include <cstring>
#include <algorithm>
using namespace std;
char s[1000005],t[2000010];
int r[2000010];
int main(){
ifstream fin("pscpld.in");
ofstream fout("pscpld.out");
if(!(fin>>s))return 0;
int ns=strlen(s);
// 1. Transformare sir: adaugam # intre litere
int n=0;
t[n++]='@';
for(int i=0;i<ns;i++){
t[n++]='#';
t[n++]=s[i];
}
t[n++]='#';
t[n++]='$';
long long tot=0;
int c=0,m=0; // c=centru, m=margine dreapta
// 2. Algoritmul Manacher
for(int i=1;i<n-1;i++){
int ogl=2*c-i; // oglinda lui i fata de c
if(i<m)r[i]=min(m-i,r[ogl]);
// Extindere fara spatii la operatori
while(t[i+(1+r[i])]==t[i-(1+r[i])])r[i]++;
// Update centru si margine
if(i+r[i]>m){
c=i;
m=i+r[i];
}
// Adaugam numarul de palindromuri gasite
tot+=(r[i]+1)/2;
}
fout<<tot;
return 0;
}