蓝桥杯2015年第六届真题-切开字符串c++使用string与map进行求解

解题思路:首先题目要求的是将字符串任意切割成两半（且两半都不能为空，说实话有一半都是空的那其实也没切对吧），然后在前一部分寻找正回文子串（长度为奇数的回文串，注意这里包括1个字符的子串）并统计下来，后一部分寻找“非正回文子串”（实际上就是所有偶数的子串加上所有奇数的非回文子串）并统计下来，两者相乘，然后保存结果取最大值；

注意注意注意！！！相同的子串只计数一次

看到这里如果你有了思路那就赶紧去写吧!如果还是不懂怎么写请看下方的代码具体操作

参考代码:

#include
#include
#include
using namespace std;
int mymax=0;//保存最大的结果 
int n;//输入时有多少个字符，（虽然用string完全不需要这个） 
int estimate(string str_es)//判断是否是回文 ，是回文返回1，不是返回0 
{
    int pd=1;
    int len=str_es.size();//求字符串长度 
        for(int i=0,j=len-1;i<=j;++i,--j)
        {
                if(str_es[i]!=str_es[j])pd=0;
        }
    return pd;
}
void dispose(string str1,string str2)//对已经分成两半的字符串进行处理 
{
    int len1=str1.size();
    int len2=str2.size();
    int cnt1=0,cnt2=0;
    map
    int k=1; //正回文子串是奇数的所以1开始 
    while(k<=len1)
    {
        for(int i=0;i<=len1-k;i++)
        {
                    string str_es1=str1.substr(i,k);//截取子串 
                    map_1[str_es1]++;//记录该子串出现了一次 
                    if(map_1[str_es1]==1)//该子串之出现一次进行判断，不是一次那肯定是重复了 不用进行判断了
                    {    
                          cnt1+=estimate(str_es1);
                    }
        }
        k+=2;//加长判断的子串的长度，奇数加偶数还是奇数；
    }
    k=1;
    while(k<=len2)
    {
        for(int i=0;i<=len2-k;i++)
        {
                     if(k%2!=0)//奇数时 
                      {
                            string str_es2=str2.substr(i,k);
                            map_2[str_es2]++;
                             if(map_2[str_es2]==1)
                             {
                                      if(estimate(str_es2)==0)cnt2++;//奇数是可能为正回文子串需要判断
                              }
                       }
                     if(k%2==0)//偶数时只需要判断是否数重复就行，偶数肯定不是正回文子串 
                     {
                               string str_es2=str2.substr(i,k);
                                map_2[str_es2]++;
                                if(map_2[str_es2]==1)cnt2++;
                      }
        }
        k+=1;
    }
    int mul=cnt1*cnt2;
    if(mul>mymax)mymax=mul;//比较结果区最大值 
} 
int main()
{
    scanf("%d",&n);
    string str;
    cin>>str;
    int len=str.size();
    for(int i=1;i<n;i++)//将字符串分为两部分 
    {
            string str1=str.substr(0,i);
            string str2=str.substr(i,len);
            dispose(str1,str2);
    } 
    cout<<mymax;
    return 0;
}

第一次写题解，写的不是很好希望审核老师能给通过，也希望看到的同学不要因为看不到来“砍我”。逃