Python真題案例之最長(zhǎng)回文子串 周期串詳解
一、最長(zhǎng)回文子串
問題描述??
大家已經(jīng)熟悉了AABCC、AABBCC這種類型的字符串是回文串。
也就是說,排除掉字符串中的各種字符,字母不區(qū)分大小寫,完成最長(zhǎng)回文子串挑選即可。 如果有幾個(gè)相同長(zhǎng)度的字符串,需要使用最左側(cè)的子串,輸出的時(shí)候原樣輸出
樣例輸入:
“Confuciuss say:Madam,I'm Adam”
樣例輸出:
“Mandam,I'm Adam”
問題分析??
第一步應(yīng)該去除原字符串內(nèi)的特殊字符得到一個(gè)只含有字母的字符串
第二步就是進(jìn)行純字母字符串中回文子串的挑選
將指定的回文字符串挑選出來還需要進(jìn)行原樣輸出
所以應(yīng)記錄一下子串首尾字符在原字符串中的坐標(biāo)。
可以定義一個(gè)數(shù)組長(zhǎng)度與純字母子串一樣長(zhǎng)。在進(jìn)行篩選空白字符的時(shí)候記錄該字符在原串的索引
代碼實(shí)現(xiàn)??
老規(guī)矩先上運(yùn)行結(jié)果:

這里使用了兩種實(shí)現(xiàn)方式,一種是c語(yǔ)言風(fēng)格一種是Python 兩者主要區(qū)別就是Python可能會(huì)有一些庫(kù)方便進(jìn)行判斷。
# C語(yǔ)言風(fēng)格實(shí)現(xiàn)
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("第一種實(shí)現(xiàn)方式:")
print(x,y)
print(mystr[charri[x]:charri[y]+1:])
# python風(fēng)格實(shí)現(xiàn)
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("第二種實(shí)現(xiàn):")
print(x,y)
print(mstr[snum[x]:snum[y-1]+1])
二、周期串
問題描述??
如果一個(gè)字符串可以由一個(gè)長(zhǎng)度為k的子串重復(fù)多個(gè)周期得到,那么我們說該串是以k為周期的周期串
例如:qweqweqwe(以3為周期),abababab(可以以2,4為周期)
我們的任務(wù)就是輸入一個(gè)字符串然后找出該串的最小周期數(shù)
樣例輸入:
HoHoHo
樣例輸出:
2
問題分析??
先是進(jìn)行字符串的讀取,然后選定一個(gè)周期,判斷字符串中下一周期子串與上一周期子串是否對(duì)應(yīng)位置相同
有一個(gè)位置不相同的就判定為不是周期串,因?yàn)檎业氖亲钚≈芷诳梢詮?開始判定 找最大周期數(shù)就從主串長(zhǎng)度開始判斷起
代碼實(shí)現(xiàn)??
老規(guī)矩先上運(yùn)行結(jié)果:

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)
???? ? ???? ???? !
到此這篇關(guān)于Python真題案例之最長(zhǎng)回文子串 周期串詳解的文章就介紹到這了,更多相關(guān)Python 最長(zhǎng)回文子串內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
Python 一行代碼能實(shí)現(xiàn)喪心病狂的功能
這篇文章主要介紹了Python 一行代碼能實(shí)現(xiàn)喪心病狂的功能,需要的朋友可以參考下2020-01-01
python對(duì)象轉(zhuǎn)字典的兩種實(shí)現(xiàn)方式示例
這篇文章主要介紹了python對(duì)象轉(zhuǎn)字典的兩種實(shí)現(xiàn)方式,結(jié)合實(shí)例形式分析了Python字典與對(duì)象數(shù)據(jù)類型轉(zhuǎn)換相關(guān)操作技巧,需要的朋友可以參考下2019-11-11
Ubuntu配置Python環(huán)境的超詳細(xì)教程
這篇文章主要給大家介紹了關(guān)于Ubuntu配置Python環(huán)境的超詳細(xì)教程,文中通過代碼示例將配置的過程介紹的非常詳細(xì),對(duì)大家學(xué)習(xí)或者使用Python具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2023-08-08
python3.x實(shí)現(xiàn)發(fā)送郵件功能
這篇文章主要為大家詳細(xì)介紹了python3.x實(shí)現(xiàn)發(fā)送郵件功能,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2018-05-05
Python之PyQt6對(duì)話框的實(shí)現(xiàn)
這篇文章主要介紹了Python之PyQt6對(duì)話框的實(shí)現(xiàn),文章內(nèi)容詳細(xì),簡(jiǎn)單易懂,小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,也給大家做個(gè)參考。一起跟隨小編過來看看吧2023-01-01
如何使用Python JSON解析和轉(zhuǎn)換數(shù)據(jù)
JSON 是文本,使用 JavaScript 對(duì)象表示法編寫,Python 有一個(gè)內(nèi)置的 json 包,可用于處理 JSON 數(shù)據(jù),本文給大家介紹使用Python JSON解析和轉(zhuǎn)換數(shù)據(jù)的方法,感興趣的朋友跟隨小編一起看看吧2023-11-11
python中使用 xlwt 操作excel的常見方法與問題
這篇文章主要給大家介紹了關(guān)于python中使用 xlwt 操作excel的常見方法與問題的相關(guān)資料,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-01-01

