首页 > 代码库 > HDU5785 manacher+差分数组
HDU5785 manacher+差分数组
用manacher算法O(n)求出所有的回文半径。有了回文半径后,就可以求出L[i]表示以i结尾的回文串的起始位置的和R[i]表示以i起始的回文串的结尾位置的和,然后就可以求出答案了,这里要注意奇偶长度回文串的不同处理。复杂度O(n)
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N = 1e6+10; 4 typedef long long ll; 5 const int mod = 1e9+7; 6 int n,m,i,r,p,f[N<<1]; char a[N],s[N<<1]; 7 ll L[N], R[N]; 8 void add(ll& a, ll b){ 9 a += b;10 if(a >= mod||a <= -mod) a %= mod;11 }12 int main(){13 while(~scanf("%s", a+1)){14 n = strlen(a+1);15 for(i = 1; i <= n; i++) s[i<<1] = a[i], s[i<<1|1] = ‘#‘;16 s[0] = ‘$‘, s[1] = ‘#‘, s[m = (n+1)<<1] = ‘@‘;17 for(r=p=0,f[1]=1,i=2;i<m;i++){18 for(f[i]=r>i?min(r-i,f[p*2-i]):1;s[i-f[i]]==s[i+f[i]];f[i]++);19 if(i+f[i]>r)r=i+f[i],p=i;20 }21 22 memset(L, 0, sizeof(ll)*(n+5));23 memset(R, 0, sizeof(ll)*(n+5));24 for(i=2;i<=2*n; i++){25 int ret = f[i]-1, pos = i/2;26 if(ret == 0) continue ;27 ret /= 2;28 if(i&1){29 //[pos+1, pos+rer/2]30 add(L[pos+1], pos), add(L[pos+2], -1-pos), add(L[pos+ret+1], ret-pos), add(L[pos+ret+2], pos+1-ret);31 //[pos-ret/2+1, pos]32 add(R[pos-ret+1], pos+ret), add(R[pos-ret+2], -1-pos-ret), add(R[pos+1], -pos), add(R[pos+2], pos+1);33 }else{34 //[pos, pos+ret/2]35 add(L[pos], pos), add(L[pos+1], -1-pos), add(L[pos+ret+1], ret-pos+1), add(L[pos+ret+2], pos-ret);36 //[pos-ret/2, pos]37 add(R[pos-ret], pos+ret), add(R[pos-ret+1], -1-pos-ret), add(R[pos+1], 1-pos), add(R[pos+2], pos);38 }39 }40 for(i=1; i<=n;i++)41 add(L[i], L[i-1]), add(R[i], R[i-1]);42 for(i=1; i<=n;i++)43 add(L[i], L[i-1]), add(R[i], R[i-1]);44 ll ans = 0;45 for(i=1;i<n;i++){46 ans += L[i]*R[i+1];47 if(ans >= mod||ans <= -mod)48 ans %= mod;49 }50 cout << (ans+mod)%mod << endl;51 }52 return 0;53 }
HDU5785 manacher+差分数组
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。