前言
今天来记录一下字符串处理中常见到的回文子串与周期串问题。使用的语言是Python
优雅的处理字符串是程序员不可或缺的技能,快来一起学习吧🪐ฅʕ•̫͡•ʔฅ
一、最长回文子串
问题描述🪐
大家已经熟悉了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)
