蓝桥杯2015年第六届真题-切开字符串

解题思路:

注意事项:

参考代码:

#include<bits/stdc++.h>

using namespace std;

int n,A,B,max_ans=-1;

string s,a,b;

int check(string str)    //用于检测字符串是否是正回文子串 

{

    if(str.length()%2==0)    //如果长度是奇数，直接判错

    {

        return 0;

    } 

    for(int i=0;i<str.length()/2;i++)    //如果不是回文，直接判错 

    {

        if(str[i]!=str[str.length()-1-i])

        return 0;

    }

    return 1;

} 

int f_front(string ss)

{

    map<string,int>    mp;    //用于标记字符串是否出现过 

    int ans=0; 

    string temp;

    for(int i=0;i<ss.length();i++)    //枚举子串起点

    {

        for(int j=1;j<=ss.length();j++)    //枚举子串长度 

        {

            temp=ss.substr(i,j);

            if(check(temp)&&!mp.count(temp))    //如果这个串是正回文并且没有出现过

            {

                mp[temp]=1;

                ans++;

            } 

        }

    }

    return ans; 

}

int f_rear(string ss)

{

    map<string,int>    mp;    //用于标记字符串是否出现过 

    int ans=0; 

    string temp;

    for(int i=0;i<ss.length();i++)    //枚举子串起点

    {

        for(int j=1;j<=ss.length();j++)    //枚举子串长度 

        {

            temp=ss.substr(i,j);

            if(!check(temp)&&!mp.count(temp))    //如果这个串不是正回文并且没有出现过

            {

                mp[temp]=1;

                ans++;

            } 

        }

    }

    return ans; 

}

int main()

{

    cin >> n;

    cin >> s;

    for(int i=1;i<=s.length()-1;i++)    //枚举前串的长度

    {

        a=s.substr(0,i);    //前串，起点是0，长度是i 

        b=s.substr(i,s.length()-i);    //后串，起点是i，长度是length-i

        //cout << "前串："+a << endl <<"后串："+ b <<endl; 

        A=f_front(a);

        B=f_rear(b);

        if(A*B>max_ans)

        {

            max_ans=A*B;

        }

    } 

    cout << max_ans << endl;

    return 0;

}