Python真題案例之最長回文子串 周期串詳解

Posted on by

一、最長回文子串

問題描述🪐

大傢已經熟悉瞭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)

ᴴᴬᵛᴱ ᴬ ᴳᴼᴼᴰ ᵀᴵᴹᴱ ！

到此這篇關於Python真題案例之最長回文子串 周期串詳解的文章就介紹到這瞭,更多相關Python 最長回文子串內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：