首页 > 试题广场 >

密码截取

[编程题]密码截取

热度指数：259428 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

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

数据范围：字符串长度满足 $1 \le n \le 2500 \$

输入描述:

输入一个字符串（字符串的长度不超过2500）

输出描述:

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

示例1

输入

ABBA

输出

示例2

输入

ABBBA

输出

示例3

输入

12HHHHA

输出

算法知识视频讲解

牛客155969019号

发表于 2021-10-15 17:47:37

str = input() n = len(str) list = [] for i in range(0,n-1): for j in range(1,n): if str[j] == str[i] and str[i+1:j] == str[j-1:i:-1]: 展开全文

古罗马哥哥古巴比伦

发表于 2022-03-25 23:09:04

# 从右到左，对每个字符进行遍历处理，并且每个字符要处理两次，因为回文子串有两种情况： # ABA型：只需要从当前字符向两边扩散，比较左右字符是否相等，找出以当前字符为中心的最长回文子串长度 # ABBA型：只需要从当前字符和下一个字符向两边扩散，比较左右字符是否相等，找出以当前字符和下一个字符为中展开全文

江南好___

发表于 2021-11-01 15:11:49

描述输入描述：输入一个字符串（字符串的长度不超过2500）输出描述：返回有效密码串的最大长度示例输入：ABBA 输出：4 知识点：字符串，指针，动态规划难度：⭐⭐⭐ 题解方法一：中心扩散法图解：解题思路：最长回文子串的中心扩散法，遍历每个字符作为中间位，进行左右比较算法展开全文

kunkun_1230

发表于 2020-04-10 11:49:52

leetcode第五题按照奇偶顺序，找到最长的list即可。代码逻辑非常简单 def longp(s): res = '' for i in range(len(s)): #先判定奇数的，从i开始左右对比 tmp = helper(s,i,i) 展开全文

摸鱼学大师

发表于 2021-10-19 23:46:14

题目的主要信息：输入一个长度不超过2500的字符串找到其中最长的回文子串长度方法一：中心扩散法具体做法：我们可以遍历每个字符串每个位置，都以其为回文子串的中心，或是奇数长度子串的中心（从两边开始找），或是偶数长度的子串中心（以它左边和它一起），分别向两边扩散，只要这个过程中两边字符是相展开全文

牛牛鸭

发表于 2021-07-14 10:40:01

输入：‘1332ABBA707’ #输入中有‘ABBA’ 、'33'、'707'三个回文子串,长度分别为4，2，3，不难发现一个规律。偶数回文串中间必然存在2位的回文子串‘XX’，奇数回文串中间必然存在3位的回文子串'XYX' 输出：4 &nbs 展开全文

为什么机器不学习

发表于 2021-01-07 21:01:45

和Leetcode 5 最长回文字是一个题，暴力解采用双指针从两侧向中心搜索，复杂度可达O（n^3）。这里我们采用中心扩散的做法，把复杂度降到O（n^2）。所谓中心扩散，就是选定一个值，然后向左右扩散。我们可以发现，回文串有两种，一种是aabb，中心在ab之间；另一种是aacbb，中心为c。我们可以展开全文