Queries for Number of Palindromes

本文主要是介绍Queries for Number of Palindromes，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

~~~~~~       Queries for Number of Palindromes ~~~~~      总题单链接

思路

~~~~~       设 $g[L][R]$ 表示区间 $[L,R]$ 是否为回文串。

~~~~~      预处理 $g$，枚举回文串的中点，从每个中点开始向两侧扩展，判断两端是否相等。

~~~~~      设 $dp[i][len]$ 表示以 $i$ 为左端点，长度为 $len$ 的区间内有多少个回文子串。

~~~~~      转移：$dp[i][len]=dp[i][len-1]+dp[i+1][len-1]-dp[i][len-2]+g[i][i+len-1]$

~~~~~      容斥原理，不能理解的可以画个图。

代码

#include<bits/stdc++.h>
#define ll int
using namespace std;string s;
ll n,dp[5005][5005],g[5005][5005];signed main(){ios::sync_with_stdio(false);cin>>s;s='.'+s;n=s.size()-1;for(ll i=1;i<=n;i++){g[i][i]=1;ll L=i-1,R=i+1;while(L>=1&&R<=n&&s[L]==s[R]){g[L][R]=1;L--,R++;}}for(ll i=1;i<n;i++){if(s[i]==s[i+1])g[i][i+1]=1;else continue;ll L=i-1,R=i+2;while(L>=1&&R<=n&&s[L]==s[R]){g[L][R]=1;L--,R++;}}for(ll i=1;i<=n;i++)dp[i][1]=1;for(ll len=2;len<=n;len++)for(ll i=1;i+len-1<=n;i++)dp[i][len]=dp[i][len-1]+dp[i+1][len-1]-dp[i+1][len-2]+g[i][i+len-1];ll Q;cin>>Q;while(Q--){ll x,y;cin>>x>>y;cout<<dp[x][y-x+1]<<endl;}return 0;
}

这篇关于Queries for Number of Palindromes的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---