一、判断回文子串

首先单个字符是true，然后我们只需要判断回文小串两边的字符是否相等就行，因为记录了小串，比挨着比好一点。

所以外层递增的是区间长度。

    for(int i = 0; i < len; i++)
        is[i][i] = true;//单个字符是回文串 
    for(int l = 1; l < len; l++)    //枚举区间长度
    for(int i = 0; i < len-l; i++)   //判断这个长度的所有串
    {
        if((l==1||is[i+1][i+l-1])&&a[i]==a[i+l])
        //回文串基础上左右添加了两个相同字符 
            is[i][i+l]=true;
    }

二、 区间内回文串数量

f[i][j]表示从i到j的子串内回文串的数量

就是从已知推未知，长子串由短子串推出，注意容斥原理

    for(int i = 0; i < len; i++) //初始化dp，单个字符先算一个 
        f[i][i] = 1;

    for(int l = 1; l < len; l++)//区间长度l
    {
        for(int i = 0; i < len-l; i++)
        {
            int j = i+l;//末位置是i+区间长
            //由右边少一位和左边少一位的两个小区间转移给大区间（减去重叠部分，容斥原理） 
            f[i][j] = f[i][j-1]+f[i+1][j]-f[i+1][j-1]+is[i][j];
            //容斥原理： dp[i][j] = dp[i+1][j]+dp[i][j-1]-dp[i+1][j-1];
        }
    }

三、Queries for Number of Palindromes

传送门：Problem - 245H - Codeforces (Unofficial mirror by Menci)

//看到n的范围很小，但是Query很多,所以提前预处理出每一段l,r的答案

三就是一二的组合了

#include #include using namespace std; char a[5100]; bool is[5100][5100]; int f[5100][5100]; int main() { while(~scanf("%s",a)) { memset(is,false, sizeof(is)); memset(f,0,sizeof(f)); int len = strlen(a); for(int i = 0; i < len; i++) is[i][i] = true;//单个字符是回文串 for(int l = 1; l < len; l++) //枚举区间长度 for(int i = 0; i < len-l; i++) //判断这个长度的所有回文串 { if((l==1||is[i+1][i+l-1])&&a[i]==a[i+l]) //回文串基础上左右添加了两个相同字符 is[i][i+l]=true; } for(int i = 0; i < len; i++) //初始化dp，单个字符先算一个 f[i][i] = 1; for(int l = 1; l < len; l++)//区间长度l { for(int i = 0; i < len-l; i++) { int j = i+l;//末位置是i+区间长 //由右边少一位和左边少一位的两个小区间转移给大区间（减去重叠部分，容斥原理） f[i][j] = f[i][j-1]+f[i+1][j]-f[i+1][j-1]+is[i][j]; //容斥原理： dp[i][j] = dp[i+1][j]+dp[i][j-1]-dp[i+1][j-1]; } } //看到n的范围很小，但是Query很多,所以提前预处理出每一段l,r的答案 int q; scanf("%d",&q); for(int i = 0; i < q; i++)//q次查询 { int l,r; scanf("%d%d", &l, &r); printf("%d\n",f[l-1][r-1]); } } return 0; } 四、疯狂星期四 利用一可以写出下面的，流程就是找出所有回文子串再统计kfc开头的。但是字符串太长了这个方法存不下。 #include<bits/stdc++.h> const int maxn=1e4+100; using namespace std; int dp[maxn][maxn]={0}; int kn=0,fn=0,cn=0; int main() { int n; cin>>n; char s[100]; scanf("%s",&s); for(int j=0;j<n;j++) { if(s[j]=='k') kn++; if(s[j]=='f') fn++; if(s[j]=='c') cn++; } for(int i=0;i<=n;i++) { dp[0][i]=1; dp[1][i]=1; } for(int i=2;i<=n;i++) { for(int j=0;j<=n-i;j++) { if((s[j]==s[j+i-1])&&(dp[i-2][j+1])) { dp[i][j]=1; if(s[j]=='k') kn++; if(s[j]=='f') fn++; if(s[j]=='c') cn++; } } } cout<<kn<<" "<<fn<<" "<<cn; } 然后补题看大家用了二分，从中心位置开始往两边走，两边各加一个字符后如果是回文串就统计一下，直到左边或者右边走不下去。 #include<bits/stdc++.h> using namespace std; int k,f,c; int n; string s; //KFC二分 void ans(int l,int r) { while(l>=0&&r<n&&s[l]==s[r]) { if(s[r]=='k') k++; if(s[r]=='f') f++; if(s[r]=='c') c++; l--;r++; } } int main() { while(cin>>n) { cin>>s; for(int i=0;i<n;i++) { ans(i,i);//字符串长度为奇数 ans(i,i+1);//字符串长度为偶数 } cout<<k<<" "<<f<<" "<<c<<endl; } return 0; } 五、分割回文串 题目：131. 分割回文串 - 力扣（LeetCode） 具体看这里：代码随想录 (programmercarl.com) #include<bits/stdc++.h> const int maxn=5e5+100; #define INF 0x3f3f3f3f typedef long long ll; using namespace std; int kn=0,fn=0,cn=0; vector<vector > result; vector ok;//已经回文的字符串； bool isPalindrome(const string& s,int l,int r)//双指针 { for(int i=l,j=r;i<j;++i,--j) { if(s[i]!=s[j]) return false; } return true; } void goback(const string&s,int index) { if(index>=s.size())//找到了分割方案 { //cout<<m<<" "<<n<<endl; //cout<<s.size()<<endl; result.push_back(ok); return; } for(int i=index;i<s.size();i++) { if(isPalindrome(s,index,i))//是回文串就截取 { string t=s.substr(index,i-index+1); //cout<<t<<endl; ok.push_back(t); } else continue; goback(s,i+1);//起始位置+1 //cout<<index<<" "<<i-index+1<<endl; ok.pop_back();//回溯过程中，弹出子串 } } int main() { ll n; cin>>n; string s; cin>>s; goback(s,0); for(auto tt:result) { for(auto t:tt) cout<<t<<" "; cout<<endl; }