題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=5157

解題思路：

我們可以先用mancher算法對字符串進行處理，把以每個點為中心的回文串半徑求出來，然后進行處理。

加入對以p為中心的點，從p-r[i]+1~p都是回文串的開頭,那么對于每個回文串（開頭是j）只要記錄結尾從1~j-1的回文串個數，我們可以用dp記錄以每個點為結尾的回文串個數，s[i]=sigma(dp[i]),則是結尾從1~j-1的回文串個數。那么對這個中心點來說一共的回文串對應該有：s[p-r[i]]+...+s[p-1]個，那么我們可以繼續用一個數組s1[i]求s[i]的前綴和，那么總復雜度是O（n）。

至于dp[i]怎么求，你已經知道了半徑，那從p~p+r[i]-1這些點的dp值都要加1，可以用樹狀數組來維護。

參考博客：http://blog.csdn.net/u013665921/article/details/42552603

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std;typedef long long LL; char c[200005],f[100005]; int r[200005],tree[200005]; LL s[200005],s1[200005];int low(int n) {return n & -n; }void merg(int p,int n,int k) {while(p<=n){tree[p]+=k;p=p+low(p);} }int sum(int p) {int s=0;while(p>0){s+=tree[p];p=p-low(p);}return s; }void mancher(int n) {int id;r[0]=1;id=0;for(int i=1; i<=2*n; i++){if(r[id]+id > i) r[i] = min(r[2*id-i],r[id]+id-i);else r[i] = 1;while(i-r[i]>=0 && i+r[i]<=2*n && c[i-r[i]]==c[i+r[i]]) r[i]++;if(i+r[i] > id+r[id])id=i;} }void get_back(int n) {memset(tree,0,sizeof(tree));for(int i=1;i<=2*n;i++){int p=i+r[i]-1;if(i%2==0){if(p>i){merg(i/2+1,n,1);merg(p/2+1,n,-1);}}else{merg((i+1)/2,n,1);merg(p/2+1,n,-1);}}s[0]=0;s1[0]=0;for(int i=1;i<=n;i++){s[i]=s[i-1]+sum(i);s1[i]=s1[i-1]+s[i];} }void work(int n) {LL ans=0;int i,j;for(i=1;i<=2*n;i++){if(i % 2 == 0 && r[i] > 1)ans+=s1[i/2-1]-s1[(i-r[i]+1)/2-1];else if(i % 2 == 1)ans+=s1[(i+1)/2-1]-s1[(i-r[i]+1)/2-1];}cout << ans << endl; }int main() {int i,j,n;while(scanf("%s",f)!=EOF){n = strlen(f);c[0] = '#';for(i=1;i<=n;i++){c[2*i] = '#';c[2*i-1] = f[i-1];}mancher(n);get_back(n);work(n);}return 0; }

總結

以上是生活随笔為你收集整理的hdu 5157(manacher+前缀和+树状数组)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。