数据结构第5章 串

第5章串classString(object):def__init__(self):self.MaxStringSize=256self.chars=""self.length=0defIsEmpty(self):#判断是否为空ifself.length==0:IsEmpty=Trueelse:IsEmpty=FalsereturnIsEmptydefCreateString(self):#创建串stringSH=input("请输入字符串：")iflen(stringSH)>self.MaxStringSize:print("溢出，超过的部分无法保存")self.chars=stringSH[:self.MaxStringSize]else:self.chars=stringsprint("输入字符串长度是：%d"%len(stringSH))defStringConcat(self,strSrc):#串连接lengthSrc=len(strSrc)stringSrc=strSrciflengthSrc+len(self.chars)<=self.MaxStringSize:self.chars=self.chars+stringSrcelse:print("两个字符的长度之和溢出，超过的部分无法显示")size=self.MaxStringSize-len(self.chars)self.chars=self.chars+stringSrc[:size]print("连接后字符串为：",self.chars)defSubString(self,iPos,length):#从iPos位置开始，取长度为length的子串ifiPos>len(self.chars)-1oriPos<0orlength<1or(length+iPos)>len(self.chars):print("无法获取")else:substr=self.chars[iPos:iPos+length]print("获取的字串为：",substr)if__name__=="__main__":string=String()print(string.IsEmpty())string.CreateString()string.StringConcat("12345")string.SubString(1,4)5.3模式匹配1BF算法defBF(s1,s2,pos=0):#BF算法i=posj=0while(i<len(s1)andj<len(s2)):if(s1[i]==s2[j]):i+=1j+=1else:i=i-j+1#目标串S的i回滚j=0#模式串Tif(j>=len(s2)):returni-len(s2)else:return0if__name__=="__main__":s1="BBCABCDABABCDABCDABDE"s2="ABCDABD"print(BF(s1,s2))2KMP算法#coding=utf-8defkmp_match(s,p):#KMP算法m=len(s);n=len(p)cur=0#起始指针curtable=partial_table(p)whilecur<=m-n:#只去匹配前m-n个foriinrange(n):ifs[i+cur]!=p[i]:cur+=max(i-table[i-1],1)#有了部分匹配表,可以一次移动多位breakelse:#如果没有从任何一个break中退出，则会执行和for对应的else#只要从break中退出了，则else部分不执行。returnTruereturnFalse#部分匹配表defpartial_table(p):'''''partial_table("ABCDABD")->[0,0,0,0,1,2,0]'''prefix=set()postfix=set()ret=[0]foriinrange(1,len(p)):prefix.add(p[:i])postfix={p[j:i+1]forjinrange(1,i+1)}ret.append(len((prefix&postfixor{''}).pop()))returnretprint(partial_table("ABCDABD"))print(kmp_match("BBCABCDABABCDABCDABDE","ABCDABD"))5.4词法分析expression="3+4*2"tokens=[]i=0whilei<len(expression):ifexpression[i].isdigit():j=iwhilei<len(expression)andexpression[i].isdigit():i+=1tokens.append(expression[j:i])else:tokens.append(expression[i])i+=1print(tokens)5.5字串统计L=int(input())s=input()dict={}count=1i=0whilei<=len(s)-L:j=L+iwhilej<=len(s):s1=s[i:j]iftuple(s1)indict:dict[tuple(s1)]+=1else:dict[tuple(s1)]=1j+=1i+=1L=sorted(dict.items(),key=lambdaitem:item[1],reverse=True)foriinL[0][0]:print(str(i),end="")5.6文本处理与编辑#定义一个文本字符串text="Thisisasampletext.Wecanperformvariousstringoperationsonit."#插入操作new_text=text[:10]+"modified"+text[10:]print(new_text)#删除操作new_text_without_word=text.replace("sample","")print(new_text_without_word)#查找操作index_of_word=text.find("string")print("Theword'string'startsatindex:",index_of_word)#替换操作replaced_text=text.replace("stringoperations","functions")print(replaced_text)5.7Anagrams问题1collections模块fromcollectionsimportCounterdefis_anagram(str1,str2):returnCounter(str1)==Counter(str2)print(is_anagram(Unclear,Nuclear))2循环方法def

anagrams(s1,s2):

i