l2-008 最长对称子串 (25 分)
时间: 2023-06-05 18:47:50 浏览: 130
题目描述:
给定一个字符串,本题要求你输出其中最长的回文子串的长度。
输入格式:
输入第一行给出一个正整数n(≤1000),是测试用例的个数。随后n行,每行给出一个长度不超过1000的、由可见ASCII码及空格组成的非空字符串。
输出格式:
对每个测试用例,输出该串最长回文子串的长度。
输入样例:
4
11111
12321
abc12321cba
aaaabaaa
输出样例:
5
5
9
7
思路分析:
对于每一个测试用例,我们可以依次遍历字符串中的每一个字符,将这个字符作为回文子串的中心,向两侧扩展,直到不能再扩展为止。然后将得到的最长回文子串的长度与已经得到的最长回文子串的长度相比较,更新最长回文子串的长度。
需要注意的是,由于回文子串的长度可能是奇数也可能是偶数,所以在遍历每个字符时,需要分别考虑以该字符为中心的奇数长度和偶数长度的回文子串。
相关问题
L2-008 最长对称子串
回答: 题目L2-008 最长对称子串是一个关于寻找字符串中最长对称子串的问题。解决这个问题的思路是首先将输入的字符串反转,然后通过动态规划的方法判断两个字符串最长的连续序列。算法的时间复杂度为O(n^2)。具体的实现可以参考博客:https://blog.csdn.net/I_O_fly/article/details/79689562。这个博客中提供了详细的代码实现和解释。通过运行这段代码,可以得到最长对称子串的长度。<span class="em">1</span><span class="em">2</span>
#### 引用[.reference_title]
- *1* *2* [PTA L2-008 最长对称子串(巨简单做法)](https://blog.csdn.net/qq_47969988/article/details/125698440)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v92^chatsearchT3_1"}}] [.reference_item style="max-width: 100%"]
[ .reference_list ]
L2-008 最长对称子串python
好的,关于 L2-008 最长对称子串,我可以给你一些思路和代码实现。
首先,对于一个字符串,我们可以枚举每一个子串,然后判断该子串是否是回文串。但是这样的时间复杂度是 $O(n^3)$,显然会超时。
因此,我们可以考虑优化。我们可以从中心向两边扩展,来判断回文串。具体来说,我们可以枚举每一个可能的中心位置,然后向两边扩展,直到不能扩展为止。这样的时间复杂度是 $O(n^2)$。
具体实现可以参考下面的代码:
```python
def longest_palindrome(s):
n = len(s)
max_len = 0
start = 0
for i in range(n):
# 以 i 为中心的奇数长度回文串
l, r = i, i
while l >= 0 and r < n and s[l] == s[r]:
l -= 1
r += 1
if r - l - 1 > max_len:
max_len = r - l - 1
start = l + 1
# 以 i 和 i+1 为中心的偶数长度回文串
l, r = i, i + 1
while l >= 0 and r < n and s[l] == s[r]:
l -= 1
r += 1
if r - l - 1 > max_len:
max_len = r - l - 1
start = l + 1
return s[start:start+max_len]
```
这个函数的输入是一个字符串,输出是该字符串的最长回文子串。
相关推荐
![c](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_lunwen.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)