首页 > 试题广场 >

密码截取

[编程题]密码截取
  • 热度指数：268080 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
\hspace{15pt}Catcher是MCA国的情报员，他工作时发现敌国会用一些对称的密码进行通信，比如像这些 \texttt{ 、\texttt{ 、\texttt{ 、\texttt{。
\hspace{15pt}但是他们有时会在开始或结束时加入一些无关的字符以防止别国破解。比如进行下列变化 \texttt{ 、\texttt{，\texttt{ 。因为截获的串太长了，而且存在多种可能的情况（ \texttt{ 可看作是 \texttt{ 或 \texttt{ 的加密形式），Cathcer的工作量实在是太大了，他只能向电脑高手求助，你能帮Catcher找出最长的有效密码串吗？

输入描述:
\hspace{15pt}在一行上输入一个长度为 1 \leqq {\rm length}(s) \leqq 2500 ，仅由大小写字母和数字构成的字符串 s ，代表截获的密码。


输出描述:
\hspace{15pt}在一行上输出一个整数，代表最长的有效密码串的长度。
示例1

输入

ABBA

输出

4

说明

\hspace{15pt}在这个样例中，没有无关字符，所以最长的有效密码串就是 \texttt{ 本身，长度为 4 。
示例2

输入

12HHHHA

输出

4

说明

\hspace{15pt}在这个样例中，最长的有效密码串是 \texttt{ ，长度为 4 。
算法知识视频讲解
添加回答
Python 3
牛客274247708号头像 牛客274247708号 
s = input()
n = len(s)

res = []

for i in range(0, n-1):
    for j in range(i, n):    
        if s[i] == s[j] and s[i:j+1] == s[i:j+1][::-1] :
            res.append(len(s[i:j+1]))
print(max(res))

发表于 2024-09-04 17:06:46 回复(0)
Python 3
氢气_头像 氢气_
没系统学过算法，硬解的，20/23用例超时了

def front_right(front_list,max_v):
    list1 = front_list
    while list1:
        if len(list1) <= max_v:
            break
        if list1 == list1[::-1]:
            max_v = max(max_v,len(list1))
        else:
            list1 = list1[1::]
    return max_v

def back_right(front_list,max_v):
    list1 = front_list
    while list1:
        if len(list1) <= max_v:
            break
        if list1 == list1[::-1]:
             max_v = max(max_v,len(list1))
        else:
            list1 = list1[0:-1]
    return max_v

while True:
    try:
        input = input()
        max_v = 2
        while len(input) > max_v:
            max_v = front_right(input,max_v)
            max_v = back_right(input,max_v)
            input = input[1:-1]
        print(max_v)
    except:
        break
发表于 2024-06-14 15:18:05 回复(0)
Python 3
牛客807120594号头像 牛客807120594号
为啥我这通过率没有到百分百啊！19/23的通过率，有没有大佬可以帮忙看看！！
pswd = str(input())
if len(pswd) <= 2500:
    length_pwsd = len(pswd)
    length = [1]
    for i in range(length_pwsd):
        j = i+1
        while i>=0 and j<=length_pwsd-1:
            if pswd[i] == pswd[j]:
                length.append(j-i+1)
                i -= 1
                j += 1
            else:
                # length.append(j-i+1)
                break
        while i-1>=0 and j<=length_pwsd-1:
            if pswd[i-1] == pswd[j]:
                length.append(j-i+2)
                i -= 1
                j += 1
            else:
                # length.append(j-i+2)
                break
           
    # print(length)
    print(max(length))
else:
    print('输入字符串过长')
发表于 2023-10-25 15:42:10 回复(0)
Python 3
牛客825357942号头像 牛客825357942号
所有情况可以归纳为步长为2或者3的情况，如果步长为2满足回文则向前一步以及向后一步看是否继续满足如此循环记录，步长为3也是这样。
 运行时间：49ms 占用内存：4732KB
a = input()
lis = []
for i in range(len(a)-1):
    if a[i:i+2] == a[i:i+2][::-1]:
        lis.append(len(a[i:i+2]))
        n = i
        m = i
        while 1:
            if a[n-1:m+3] == a[n-1:m+3][::-1]:
                lis.append(len(a[n-1:m+3]))
                n -=1
                m +=1
            else:
                break
    if a[i:i+3] == a[i:i+3][::-1]:
        lis.append(len(a[i:i+3]))
        n = i
        m = i
        while 1:
            if a[n-1:m+4] == a[n-1:m+4][::-1]:
                lis.append(len(a[n-1:m+4]))
                n -=1
                m +=1
            else:
                break
print(max(lis))
发表于 2023-07-28 19:02:05 回复(0)
Python 3
头顶两座山头像 头顶两座山 
input1 = input()
def count_len(lis,idx,l,flag=0):
    if idx==0:
        return 0
    for i in range(1,l+1):
        if lis[idx-i]==lis[idx+i+flag]:
            if i==l:
                return 2*l
            else:
                continue
        else:
            return 2*(i-1)
res = 2 if input1[0]==input1[1] else 1
for i in range(1,len(input1)-1):
    if input1[i]==input1[i+1]:
        n_even = min(i,len(input1)-i-1-1)
        n_odd = min(i,len(input1)-i-1)
        res = max(res,count_len(input1,i,n_even,1)+2,count_len(input1,i,n_odd)+1)
    else:
        n = min(i,len(input1)-i-1)
        res = max(res,count_len(input1,i,n)+1)
print(res)

发表于 2023-07-11 22:51:11 回复(0)
Python 3
给个抄底的机会啊头像 给个抄底的机会啊
中心扩散算法
def process(string):
    str_len = len(s)
    max_len = 0
    for i in range(str_len):
        l_len, r_len = 0, 0
        l = i-1
        r = i+1
        while l>=0 and s[i]==s[l]:
            max_len = max(max_len, i-l+1)
            l-=1
        while r<str_len and s[i]==s[r]:
            max_len = max(max_len, r-i+1)
            r+=1
        while l>=0 and r<str_len and s[l]==s[r]:
            max_len = max(max_len, r-l+1)
            r+=1
            l-=1
    print(max_len)
       



s = input()
process(s)

发表于 2023-04-10 10:56:44 回复(0)
Python 3
牛客196128295号头像 牛客196128295号 
def MaxSub(pwd):
    if len(pwd) < 1&nbs***bsp;len(pwd) > 2500:
        return False
    
    lenSub = []
    for i in range(1,len(pwd)):
        for j in range(len(pwd),i,-1):
            sub = pwd[i:j]
            if sub == sub[::-1] and len(sub) > 1:
                lenSub.append(len(sub))
    print(max(lenSub))

if __name__ == '__main__':
    pwd = input()
    MaxSub(pwd)
超时了，但想不出其他方式

发表于 2023-03-23 00:21:27 回复(0)
Python 3
甜美的马后炮炮手在迎接offer头像 甜美的马后炮炮手在迎接offer 
# 这道题就是提取回文串
print('解法1-定轴动区间的方法:')
# 求最长回文子串
line = input().strip()
newline = '#'+'#'.join(line)+'#'
RL = [1 for i in range(0, len(newline))]
for pox in range(0, len(newline)):  # 确定回文子串的中心轴的位置
    for walker in range(0, pox+1):
        if newline[pox-walker:pox+1] == newline[pox:pox+walker+1][::-1]:
            RL[pox] = walker
        else:
            break  # 当对称的2段字符不等时，就停止当前循环的执行，需要换一个pox

maxRL = max(RL)
if maxRL>=2:
    # 根据轴心位置与最大的轴半径
    longstr = newline[RL.index(maxRL)-maxRL:RL.index(maxRL)+maxRL].replace('#','')
    print(longstr)
    print(len(longstr))


# 解法2
# 采用双指针的方法
print('解法2-采用双指针截取片段的方法:')
str_input = input()
if str_input == str_input[::-1]:
    print(len(str_input))
else:
    data_list = []
    for i in range(len(str_input)-1):
        for j in range(1, len(str_input)):
            if str_input[i] == str_input[j] and str_input[i+1:j] == str_input[j-1:i:-1]:
                data_list.append(len(str_input[i:j+1]))
    print(max(data_list))


# 解法3-使用动态规划
print('解法3-使用动态规划:')
## 使用动态规划
nums = input().strip()

n = len(nums)
# 用 dp 矩阵记录nums子序列的状态
# 若 dp[i][j] = True，表示 nums[i:j+1] 为回文串
#    dp[i][j] = False，表示 nums[i:j+1] 不是回文串
dp = [[False] * n for _ in range(n)]
# 由于单个字符均是回文串，所以设置dp[i][j]为True。且 j>=i ，即dp的下三角全是不能用的
for i in range(n):
    dp[i][i] = True

max_len = 1  # 初始化最大长度
start = 0  # 初始化最长回文串的起始位置

# 已经设置对角线上的状态全为 True，这里从索引 1 开始
for j in range(1, n):
    # 满足 j > i
    for i in range(j):
        # 如果dp[i][j] <= 2，意味着nums[i:j+1]为回文串的前提是两端相等。
        if j-i <= 2:
            if nums[j] == nums[i]:
                # 更新状态 和 计算当前长度
                dp[i][j] = True
                curent_len = j-i + 1
        else:
            # 如果dp[i][j] > 2，意味着nums[i:j+1]为回文串的前提是两端相等 和 nums[i+1:j]也是回文串。
            if nums[j] == nums[i] and dp[i+1][j-1]:
                dp[i][j] = True
                curent_len = j-i + 1

        # 如果是回文串，比较当前长度和之前长度的大小，变大更新最大长度和起始位置。
        if dp[i][j]:
            if curent_len > max_len:
                max_len = curent_len
                start = i
# 通过最大长度和起始索引计算回文串。
# print(nums[start:start + max_len])
print(len(nums[start:start + max_len]))
# print(max_len)

发表于 2023-03-18 12:46:07 回复(1)
Python 3
Aprilhahaha头像 Aprilhahaha 
while True:
    try:
        s = input()
        n = len(s)
        if s==s[::-1]:
            print(n)
        else:
            maxsize = []
            for i in range(n-1):
                for j in range(i+1,n):
                    if s[j] == s[i] and s[i:j+1]==s[j:i-1:-1]:
                        maxsize.append(len(s[i:j+1]))
#                         maxsize = max(maxsize, len(s[i:j]))
            print(max(maxsize))
    except:
        break

发表于 2022-09-13 00:43:16 回复(0)
Python 3
牛客524132996号头像 牛客524132996号
ss = input()
s_list = ""
"asdaa"
for i in range(len(ss)):
    num = i if i < len(ss) - i else len(ss) - i
    num2 = i if i < len(ss)-i-1 else len(ss)-i-1
    for j in range(num+1):
#         print(ss[i-j:i+1],"asdf",ss[i+j:i-1:-1])
#         作为一个新手，这里截取字符串时，往左边i-j开始到i+1，往右边i+j开始，i-1结束，步长-1，左闭右开
        if ss[i-j:i+1] == ss[i+j:i-1:-1]:
            if len(s_list) < len(ss[i-j:i+j+1]):
                s_list = ss[i-j:i+j+1] 
    for j in range(num2+1):
#         print(ss[i-j:i+1],"asdf",ss[i+j:i-1:-1])
#         作为一个新手，这里截取字符串时，往左边i-j开始到i+1，往右边i+j开始，i-1结束，步长-1，左闭右开
        if ss[i-j:i+1] == ss[i+j+1:i:-1]:
            if len(s_list) < len(ss[i-j:i+j+2]):
                s_list = ss[i-j:i+j+2]
print(len(s_list))
发表于 2022-09-02 20:37:09 回复(1)
Python 3
蔡泽钦头像 蔡泽钦
超时了，难受
s = input()
maxlen = 0
for i in range(len(s)): # i表示截取子串的起始索引
    for j in range(i, len(s)): # j表示截取子串的终止索引
        if s[i: j+1] == s[i: j+1][::-1]:
            maxlen = max(maxlen, j+1-i)
print(maxlen)
发表于 2022-08-24 22:35:59 回复(0)
Python 3
Justinshadow头像 Justinshadow
我这个代码只能过17个用例，到长度1712的用例就超时了，大佬们能帮忙看看还能怎么优化吗？ 
s = input()
n = len(s)
dp = [[0 for _ in range(n)]for _ in range(n)]
dp[n-1][n-1]=1
for i in range(n-1):
    dp[i][i]=1
    dp[i][i+1] = 2 if s[i]==s[i+1] else 1
for L in range(n-3,-1,-1):
    for R in range(L+2,n):
        temp = s[L:R+1]
        dp[L][R] = max(dp[L+1][R],dp[L][R-1])
        if temp==temp[::-1]:
            dp[L][R]=max(dp[L][R],len(temp))
print(dp[0][n-1])

发表于 2022-08-18 15:20:45 回复(0)
Python 3
牛客167042955号头像 牛客167042955号
# if i<k and str[str.index(i):str.index(k):1]==str[str.index(k)-1:str.index(i)-1:-1]:
 #           d.append(str[str.index(i):str.index(k):1])
'''
方法1
str=input()
c=len(str)
d=[]
for i in str:
    for k in str[-1::-1]:
        if i==0 and k!=c-1:
            if str[0:k+1:1]==str[k-c::-1]:
                d.append(str[0:k+1:1])
        elif i!=0 and k==c-1:
            if str[i::1]==str[k-c:i-c-1:-1]:
                d.append(str[i::1])
        elif i==0 and k==c-1:
            if str[0::1]==str[-1::-1]:
                d.append(str[0::1])
        else:
            if str[i:k+1:1]==str[k-c:i-c-1:-1]:
                d.append(str[i:k+1:1])
print(d)
            
'''
#方法2
str1=input()
a=len(str1)
b=[]
for i in range(0,a):
    for j in range(0,a):
        if i==0 and j==0 and str1[0::1]==str1[-1::-1]:
            b.append(len(str1[0::1]))
            break#为啥不起作用
        if i==0 and j!=0 and str1[0:a-j]==str1[a-j-1::-1]:
            b.append(len(str1[0:a-j]))
        elif i!=0 and j==0 and str1[i::1]==str1[-1:i-1:-1]:
            b.append(len(str1[i::1]))
        elif str1[i:a-j]==str1[a-j-1:i-1:-1]:   
            b.append(len(str1[i:a-j]))
        else:
            continue
print(max(b))           

       

发表于 2022-08-18 01:10:16 回复(0)
Python 3
今天学习了吗~头像 今天学习了吗~
python考试时，超时有没有分呢？？看有很多答案时也是这个思路，为啥他们的就不超时？？

while True:
    try:
        a=input()
        c=[]
        for j in range(len(a)):
            for x in range(j+1,len(a)+1):
                if a[j:x]==a[j:x][::-1]:
                    c.append(len(a[j:x]))
        print(max(c))
    except:
        break
发表于 2022-07-24 17:05:15 回复(0)
Python 3
牛客346835449号头像 牛客346835449号
strs = input()
n = len(strs)
list = []
for i in range(n-1,0, -1):
    j = strs.index(strs[i])
    while j < i:
        if strs[j+1:i] == strs[i-1:j:-1]:
            list.append(i-j+1)
            break
        else:
            j = strs.index(strs[i], j+1)
print(max(list))
发表于 2022-07-21 17:21:55 回复(0)
Python 3
AlexLyn_00头像 AlexLyn_00
python3 ABA ABBA 
def judge(code, left, right):
    length_code = len(code)
    while left >= 0 and right < length_code and code[left] == code[right]:
        left = left - 1
        right = right + 1
    return right-left-1

while True:
    try:
        code = input()
        length_code = len(code)
        output = 0
        for i in range(length_code):
            output_ABA = judge(code, i, i)
            output_ABBA = judge(code, i, i+1)
            output = max(output, output_ABA, output_ABBA)
        print(output)
        
    except:
        break


发表于 2022-07-15 00:10:10 回复(0)
提交观点

问题信息

动态规划 字符串
难度：
61条回答 43444浏览

热门推荐

通过挑战的用户

查看代码

相关试题

密码截取

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号