蓝桥杯2015年第六届真题-切开字符串-题解（C语言代码）

1.正回文子串：奇数，且回文数；

2.非正回文子串：偶数的回文子串，或 不是回文子串；

3.整体把握：

在for循环的状态下，首先将字符串s利用substr()分割两个子字符串a,b；a作为前串需求解其正回文子串个数，b作为后串求解其非正回文子串；然后分别将a字符串分割成各个字符串，进行枚举判断是否为正回文子串，利用set进行优化如果此时的字符串已经存在于set中的字符串，不需要将A++;b字符串同理；每次需要更新一下max的结果，直到for循环结束。

4.substr()函数用法

#include<iostream>
#include<set>
#include<string>
using namespace std;
string s,a,b;
int n,A,B;
int check(string str){
	int len=str.length();
	if(len%2==0){//如果长度是偶数，返回0 
		return 0;
	}
	//长度是奇数，但不是回文数 
	for(int i=0;i<len/2;i++){//表示比较次数 
	    if(str[i]!=str[len-1-i]){ 
	    	return 0;
	    } 
	}
	return 1;
}
int main(){
	cin>>n;
	cin>>s;
	int len=s.length(); 
	int max=-1;
	for(int i=1;i<=len-1;i++){
	  //截取前端长度的范围 ：可以截取1,2,3,...,len-1 保证前后串不是非空 
		a=s.substr(0,i);//从下标为0开始截取长度为i;
		b=s.substr(i,len-i);//从下标为i开始截取长度为len-i; 
		set<string> st;
		string temp;
		A=0,B=0;
		//对string a,b中子串的回文情况研究
		int la=a.length();
		for(int i=0;i<la;i++){
			for(int k=1;k<=la-i;k++){//表示截取长度 
			   temp=a.substr(i,k);
			   if(check(temp)&&!st.count(temp)){
			   	// 奇数回文数&&没有在st集合中出现过
				    st.insert(temp);
				    A++; 
			   }
			}
		}
		//A表示前串中正回文子串长度
		int lb=b.length();
		for(int i=0;i<lb;i++){
			for(int k=1;k<=lb-i;k++){
				temp=b.substr(i,k);
				if(!check(temp)&&!st.count(temp)){
					st.insert(temp);
					B++;
				}
			}
		} 
		if(A*B>max){
			max=A*B;
		}	
	}
	cout<<max<<endl;
	return 0;
}