We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
#include<bits/stdc++.h>usingnamespacestd;#define ll long long#define mod 1000000007#define L 5000011intsa[L];intsai[L];intlcp[L];intv[L];chars[L];llts[L];intp[L<<1];chart[L<<1];intm,n;set<ll>found;boolscomp(inti,intj){returns[i]<s[j];}booltscomp(inti,intj){returnts[i]<ts[j];}voidget_suffix_array(){for(inti=0;i<n;i++)v[i]=i;sort(v,v+n,scomp);sai[v[0]]=1;for(inti=1;i<n;i++){if(s[v[i]]==s[v[i-1]]){sai[v[i]]=sai[v[i-1]];}else{sai[v[i]]=i+1;}}for(intp=1;p<=n;p<<=1){for(inti=0;i<n-p;i++)ts[i]=sai[i]*(n+1LL)+sai[i+p];for(inti=n-p;i<n;i++)ts[i]=sai[i]*(n+1LL);sort(v,v+n,tscomp);sai[v[0]]=1;for(inti=1;i<n;i++){if(ts[v[i]]==ts[v[i-1]]){sai[v[i]]=sai[v[i-1]];}else{sai[v[i]]=i+1;}}}for(inti=0;i<n;i++)sai[i]--;for(inti=0;i<n;i++)sa[sai[i]]=i;}voidget_lcp(){for(inti=0;i<n;i++)lcp[i]=0;intl=0;for(inti=0;i<n-1;i++){intk=sai[i];intj=k?sa[k-1]:sa[n-1];while(j+l<nands[i+l]==s[j+l]){l++;}lcp[k]=l;if(l>0){l--;}}}voidmanacher(){// from wikipedia// t has been processedintcenter=0,end=0,left=0,right=0;for(inti=1;i<m;i++){if(i>end){p[i]=0;left=i-1;right=i+1;}else{intj=2*center-i;// index on the other sideif(p[j]<end-i){// whole palindrome is insidep[i]=p[j];left=-1;// so we don't enter the loop below}else{p[i]=end-i;right=end+1;left=2*i-right;}}while(left>=0andright<mandt[left]==t[right]){p[i]++;left--;right++;}if(i+p[i]>end){center=i;end=i+p[i];}}}structNode{inti,j,v;Node*p,*l,*r;Node(inti,intj,Node*p=NULL):i(i),j(j),p(p){if(j-i==1){l=r=NULL;v=lcp[i];}else{intk=i+j>>1;l=newNode(i,k,this);r=newNode(k,j,this);v=min(l->v,r->v);}}};intnode_minocc(Node*node,intv,inti){// find maximum j, 0 <= j <= i such that a[j] < vwhile(node->l){if(i<node->l->j){node=node->l;}else{node=node->r;}}// now node->i = i < node->j = i+1if(node->v<v){returnnode->i;}while(true){while(node->pandnode->p->l==node){node=node->p;}if(!node->p){return0;}node=node->p;if(node->l->v<v){node=node->l;break;}}while(node->l){if(node->r->v<v){node=node->r;}else{node=node->l;}}returnnode->i;}intnode_maxocc(Node*node,intv,inti){// find maximum j, i <= j <= n such that a[j] >= vif(i==n){returnn;}while(node->l){if(i<node->l->j){node=node->l;}else{node=node->r;}}// now node->i = i < node->j = i+1if(node->v<v){returnnode->i;}while(true){while(node->pandnode->p->r==node){node=node->p;}if(!node->p){returnn;}node=node->p;if(node->r->v<v){node=node->r;break;}}while(node->l){if(node->l->v<v){node=node->l;}else{node=node->r;}}returnnode->i;}intmain(){scanf("%s",s);n=strlen(s);// suffix treeget_suffix_array();get_lcp();Node*root=newNode(0,n);m=0;for(inti=0;i<n;i++){t[m++]='#';t[m++]=s[i];}t[m++]='$';t[0]='^';manacher();llans=0;for(inti=1;i<m-1;i++){intk=p[i];if(t[i-k]=='#')k--;for(;k>=0;k-=2){intstart=sai[i-k>>1];intmino=node_minocc(root,k+1,start);llhsh=k*(n+1LL)+mino;if(found.find(hsh)!=found.end()){break;}found.insert(hsh);intmaxo=node_maxocc(root,k+1,start+1);llc=maxo-mino;ans+=c*(c-1);ans%=mod;}}ans=ans*(mod+1>>1)%mod;printf("%lld\n",ans);}
Palindromic Border
You are viewing a single comment's thread. Return to all comments →
C++ code, all test cases passed -