Pagini recente » Cod sursa (job #2594117) | Cod sursa (job #2118131) | Cod sursa (job #3188501) | Rezultatele filtrării | Cod sursa (job #3302773)
#include <fstream>
#include <map>
using namespace std;
ifstream cin("pscpld.in");
ofstream cout("pscpld.out");
///#define int long long
struct node{
int lung;
map <int, int> next;
int suf; int cnt;
};
node root1,root2;
node v[1000001];
int cur,poz;
string s;
void insertie(int ind){
int aux=cur,curl;
while(true){
curl=v[aux].lung;
if(ind-curl>=1 && s[ind]==s[ind-curl-1]) break;
aux=v[aux].suf;
}
if(v[aux].next.count(s[ind]-'a')){
///cout<<"a";
cur=v[aux].next[s[ind]-'a'];
v[cur].cnt++;
return ;
}
poz++;
v[aux].next[s[ind]-'a']=poz;
v[poz].lung=v[aux].lung+2;
v[poz].cnt=1;
aux=v[aux].suf;cur=poz;
if(v[cur].lung==1){
v[cur].suf=2;
return;
}
while(true){
curl=v[aux].lung;
if(ind-curl>=1 && s[ind]==s[ind-curl-1]) break;
aux=v[aux].suf;
}
v[cur].suf=v[aux].next[s[ind]-'a'];
}
signed main()
{
int i;
long long rasp=0;
root1.lung=-1;root2.lung=0;
root1.suf=root2.suf=1;
v[1]=root1;v[2]=root2;
poz=2;cur=1;
cin>>s;
for(i=0;i<s.size();i++){
insertie(i);
}
for(i=poz;i>=3;i--) {
v[v[i].suf].cnt+=v[i].cnt;
}
for(i=3;i<=poz;i++){
rasp+=v[i].cnt;///cout<<v[i].cnt<<" ";
}
cout<<rasp;
return 0;
}