Python真题案例之最长回文子串 周期串详解
作者:酷尔。 时间:2021-12-01 02:57:02
一、最长回文子串
问题描述🪐
大家已经熟悉了AABCC、AABBCC这种类型的字符串是回文串。
也就是说,排除掉字符串中的各种字符,字母不区分大小写,完成最长回文子串挑选即可。 如果有几个相同长度的字符串,需要使用最左侧的子串,输出的时候原样输出
样例输入:
“Confuciuss say:Madam,I'm Adam”
样例输出:
“Mandam,I'm Adam”
问题分析🪐
第一步应该去除原字符串内的特殊字符得到一个只含有字母的字符串
第二步就是进行纯字母字符串中回文子串的挑选
将指定的回文字符串挑选出来还需要进行原样输出
所以应记录一下子串首尾字符在原字符串中的坐标。
可以定义一个数组长度与纯字母子串一样长。在进行筛选空白字符的时候记录该字符在原串的索引
代码实现🪐
老规矩先上运行结果:
这里使用了两种实现方式,一种是c语言风格一种是Python 两者主要区别就是Python可能会有一些库方便进行判断。
# C语言风格实现
import sys
mystr=sys.stdin.readline().strip()
charr=""
charri=[]
mymax=-1
x=0
y=0
flag=True
j=-1
for i in mystr:
j+=1
if ord(i)<65 or ord(i)>122:
continue
else:
charr+=i
charri.append(j)
charr=charr.lower()
# print(charr,charri)
i=0
while i<len(charr):
j=i
while j<len(charr):
k=i
while k<=j:
if charr[k]!=charr[i+j-k]:
flag=False
break
k+=1
if flag:
if mymax<j-i+1:
mymax=j-i+1
x=i
y=j
flag=True
j+=1
i+=1
print("第一种实现方式:")
print(x,y)
print(mystr[charri[x]:charri[y]+1:])
# python风格实现
import sys
mstr=sys.stdin.readline().strip()
tstr=""
snum=[]
smax=0
x=0
y=0
j=0
for i in mstr:
if ord(i)>=65 and ord(i)<=122:
tstr+=i
snum.append(j)
j+=1
tstr=tstr.lower()
for i in range(len(tstr)):
for j in range(i,len(tstr)+1):
if tstr[i:j]==tstr[i:j][::-1] and len(tstr[i:j])>smax:
smax=len(tstr[i:j])
x=i
y=j
print("第二种实现:")
print(x,y)
print(mstr[snum[x]:snum[y-1]+1])
二、周期串
问题描述🪐
如果一个字符串可以由一个长度为k的子串重复多个周期得到,那么我们说该串是以k为周期的周期串
例如:qweqweqwe(以3为周期),abababab(可以以2,4为周期)
我们的任务就是输入一个字符串然后找出该串的最小周期数
样例输入:
HoHoHo
样例输出:
2
问题分析🪐
先是进行字符串的读取,然后选定一个周期,判断字符串中下一周期子串与上一周期子串是否对应位置相同
有一个位置不相同的就判定为不是周期串,因为找的是最小周期可以从1开始判定 找最大周期数就从主串长度开始判断起
代码实现🪐
老规矩先上运行结果:
import sys
mmax=0
mystr=sys.stdin.readline().strip()
for i in range(1,len(mystr)):
if len(mystr)%i==0:
for j in range(0,len(mystr)//i-1):
if mystr[j*i:j*i+i]!=mystr[(j+1)*i:(j+1)*i+i]:
# print(mystr[j*i:j*i+i],"--",len(mystr[(j+1)*i:(j+1)*i+i]))
break
else:
mmax=i
if mmax!=0:
break
print(mmax)
ᴴᴬᵛᴱ ᴬ ᴳᴼᴼᴰ ᵀᴵᴹᴱ !
来源:https://blog.csdn.net/apple_51931783/article/details/123239381
标签:Python,回文子串,周期串
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
Python Django ORM与模型详解
2022-01-03 10:40:53
![](https://img.aspxhome.com/file/2023/6/91876_0s.png)
Python多分支if语句的使用
2022-07-17 17:52:54
python实现八大排序算法(1)
2022-05-20 08:17:47
![](https://img.aspxhome.com/file/2023/6/130996_0s.jpg)
mysql数据表和数据表关联
2010-12-03 16:00:00
Python时间序列缺失值的处理方法(日期缺失填充)
2023-04-13 07:39:18
Python3获取拉勾网招聘信息的方法实例
2022-06-28 00:57:11
![](https://img.aspxhome.com/file/2023/3/112803_0s.jpg)
python使用7z解压软件备份文件脚本分享
2023-05-22 19:30:29
pyinstaller封装exe的操作
2021-02-12 03:21:16
![](https://img.aspxhome.com/file/2023/4/97694_0s.jpg)
python GUI库图形界面开发之PyQt5结合Qt Designer创建信号与槽的详细方法与实例
2021-09-24 03:11:51
![](https://img.aspxhome.com/file/2023/7/72087_0s.png)
Nginx搭建HTTPS服务器和强制使用HTTPS访问的方法
2021-06-26 12:42:36
![](https://img.aspxhome.com/file/2023/7/120297_0s.jpg)
python基础学习之组织文件
2022-04-08 21:47:23
![](https://img.aspxhome.com/file/2023/0/127910_0s.png)
Python 递归式实现二叉树前序,中序,后序遍历
2022-09-22 17:38:32
![](https://img.aspxhome.com/file/2023/7/66777_0s.png)
asp如何对文件进行操作?
2009-11-20 18:31:00
![](https://img.aspxhome.com/file/UploadPic/200911/20/20091120184513823s.gif)
Python及PyCharm下载与安装教程
2022-10-04 08:19:54
![](https://img.aspxhome.com/file/2023/3/90433_0s.png)
23个MySQL数据库安全使用技巧
2007-10-26 16:02:00
python写入文件如何取消自动换行
2023-11-28 22:39:11
Python中的Numpy矩阵操作
2021-10-06 07:19:23
php.ini修改php上传文件大小限制的方法详解
2023-09-11 04:03:12
浅谈Python函数式编程的返回函数与匿名函数
2021-02-22 13:40:36
腾讯注册页面的 JS 解密
2009-11-18 12:50:00