【牛客网华为机试】HJ32 密码截取

题目

描述

Catcher是MCA国的情报员，他工作时发现敌国会用一些对称的密码进行通信，比如像这些ABBA，ABA，A，123321，但是他们有时会在开始或结束时加入一些无关的字符以防止别国破解。比如进行下列变化 ABBA->12ABBA,ABA->ABAKK,123321->51233214　。因为截获的串太长了，而且存在多种可能的情况（abaaab可看作是aba,或baaab的加密形式），Cathcer的工作量实在是太大了，他只能向电脑高手求助，你能帮Catcher找出最长的有效密码串吗？

本题含有多组样例输入。

输入描述：

输入一个字符串

输出描述：

返回有效密码串的最大长度

示例1

输入：

ABBA
           

输出：

4
           

解题思路

（1）按题目要求即找到从中间位置开始往左右两边扩展能保持对称的最大字符串长度

（2）字符串长度为偶数时，对称中线左右两边的字符相等，即

string[i] == string[i+1]
           

（3）字符串长度为奇数时，对称中心字符左右两边的字符相等，即

string[i-1] == string[i+1]
           

（4）从中心点index出发，向两边寻找，元素相等则最大长度+2，否则输出当前最大长度

代码

def max_len(string):
    abba = []
    aba = []
    #遍历寻找对称位置
    for i in range(len(string)-1):
        current = i
        next_one = i+1
        if string[current] == string[next_one]:
            abba.append(i)
        elif string[current-1] == string[next_one]:
            aba.append(i)
    length = []
    for j in abba:
        first = j
        last = j+1
        while first>=0 and last<len(string) and string[first]==string[last]:
            first+=-1
            last+=1
            #CABBA，第一循环时，符合条件的只有2个字符，而此时last-first=3,所以需要减去1
            length.append(last-first-1)
    for k in aba:
        first = k-1
        last = k+1
        while first>=0 and last<len(string) and string[first] == string[last]:
            first+=-1
            last +=1
            length.append(last-first-1)
    if len(length)==0:
        return 0
    else:
        return max(length)

while True:
    try:
        string = input()
        print(max_len(string))
    except:
        break
                
            
           

Reference

https://www.nowcoder.com/ta/huawei/