Python真題案例之最長回文子串 周期串詳解
一、最長回文子串
問題描述??
大家已經(jīng)熟悉了AABCC、AABBCC這種類型的字符串是回文串。
也就是說,排除掉字符串中的各種字符,字母不區(qū)分大小寫,完成最長回文子串挑選即可。 如果有幾個(gè)相同長度的字符串,需要使用最左側(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ù)組長度與純字母子串一樣長。在進(jìn)行篩選空白字符的時(shí)候記錄該字符在原串的索引
代碼實(shí)現(xiàn)??
老規(guī)矩先上運(yùn)行結(jié)果:
這里使用了兩種實(shí)現(xiàn)方式,一種是c語言風(fēng)格一種是Python 兩者主要區(qū)別就是Python可能會(huì)有一些庫方便進(jìn)行判斷。
# C語言風(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è)長度為k的子串重復(fù)多個(gè)周期得到,那么我們說該串是以k為周期的周期串
例如:qweqweqwe(以3為周期),abababab(可以以2,4為周期)
我們的任務(wù)就是輸入一個(gè)字符串然后找出該串的最小周期數(shù)
樣例輸入:
HoHoHo
樣例輸出:
2
問題分析??
先是進(jìn)行字符串的讀取,然后選定一個(gè)周期,判斷字符串中下一周期子串與上一周期子串是否對應(yīng)位置相同
有一個(gè)位置不相同的就判定為不是周期串,因?yàn)檎业氖亲钚≈芷诳梢詮?開始判定 找最大周期數(shù)就從主串長度開始判斷起
代碼實(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真題案例之最長回文子串 周期串詳解的文章就介紹到這了,更多相關(guān)Python 最長回文子串內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
Python 一行代碼能實(shí)現(xiàn)喪心病狂的功能
這篇文章主要介紹了Python 一行代碼能實(shí)現(xiàn)喪心病狂的功能,需要的朋友可以參考下2020-01-01python對象轉(zhuǎn)字典的兩種實(shí)現(xiàn)方式示例
這篇文章主要介紹了python對象轉(zhuǎn)字典的兩種實(shí)現(xiàn)方式,結(jié)合實(shí)例形式分析了Python字典與對象數(shù)據(jù)類型轉(zhuǎn)換相關(guān)操作技巧,需要的朋友可以參考下2019-11-11Ubuntu配置Python環(huán)境的超詳細(xì)教程
這篇文章主要給大家介紹了關(guān)于Ubuntu配置Python環(huán)境的超詳細(xì)教程,文中通過代碼示例將配置的過程介紹的非常詳細(xì),對大家學(xué)習(xí)或者使用Python具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2023-08-08python3.x實(shí)現(xiàn)發(fā)送郵件功能
這篇文章主要為大家詳細(xì)介紹了python3.x實(shí)現(xiàn)發(fā)送郵件功能,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2018-05-05如何使用Python JSON解析和轉(zhuǎn)換數(shù)據(jù)
JSON 是文本,使用 JavaScript 對象表示法編寫,Python 有一個(gè)內(nèi)置的 json 包,可用于處理 JSON 數(shù)據(jù),本文給大家介紹使用Python JSON解析和轉(zhuǎn)換數(shù)據(jù)的方法,感興趣的朋友跟隨小編一起看看吧2023-11-11python中使用 xlwt 操作excel的常見方法與問題
這篇文章主要給大家介紹了關(guān)于python中使用 xlwt 操作excel的常見方法與問題的相關(guān)資料,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-01-01