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

解题思路:

此题主要是明白题目所说的非正回文串到底是什么，正回文串的定义是长度为奇数的回文串，那么非正回文串便是任意字符串，如果任意字符串为回文串，那么字符个数一定是偶数（根据命题符号化的的知识可以得知），那么在一次对字符串的分割中，会进行如下的判断：

1、对于左边的字符串，统计的正回文串，即个数为奇数，且为回文串的子字符串的个数；

2、对于右边的字符串，可以归纳为统计具有以下特点的子字符串：

    a、若字符数为偶数，无论是否是回文字符串还是普通字符串，皆成立，直接统计；

    b、若字符数为奇数，对于回文字符串不计入统计，普通字符串计入统计；

然后将上述对左右两边的统计结果进行相乘，寻找最大值，细节看代码！

注意事项:

参考代码:

def reverse(s)://将字符串进行颠倒的一个函数，单独封装。类似于列表的reverse函数

    s=list(s)

    s.reverse()

    s=''.join(s)

    return s

while True:

    try:

        a=int(input())

        b=input().strip()

        ans=[]

        for i in range(1,a):

            string1=b[0:i]

            string2=b[i:]//对字符串进行分割

            single=[j for j in range(i+1) if j%2==1]//为了方便统计正回文串的个数，将奇数装起来

            aset=set()

            bset=set()

            for j in single://第一层循环，表示子字符串的字符个数

                for k in range(len(string1))://第二层循环，暴力枚举了所有可能的情况（字符数为j），进行判断统计

                    if k+j>len(string1):

                        break

                    temp=string1[k:k+j]

                    if len(temp)==1:

                        aset.add(temp)

                    else://判断是否回文

                        temp1=temp[0:int(len(temp)/2)]

                        temp2=reverse(temp[int(len(temp)/2)+1:])

                        if temp1==temp2:

                            aset.add(temp)

            for j in range(2,len(string2)+1)://也是字符个数，对于只有1个字符的字符串，必然是正回文串，从2开始

                for k in range(len(string2))://暴力枚举所有情况

                    if k+j>len(string2):

                        break

                    if j%2==0:

                        bset.add(string2[k:k+j])

                    if j%2==1:

                        temp=string2[k:k+j]

                        temp1=temp[0:int(len(temp)/2)]

                        temp2=reverse(temp[int(len(temp)/2)+1:])

                        if temp1!=temp2:

                            bset.add(temp)

            ans.append(len(aset)*len(bset))

        print(max(ans))

    except:

        break