接上篇文章, 这里完成改文章的后部分, 以python
编写的版本
正文如下
同时,我也对原先写的python代码进行了修改,使用KMP算法
其python
实现的KMP
算法核心代码如下
def kmpSearchStrByStr(totalStr, strSearch, kmpTable):
#kmp算法查找
#返回字符串中包含搜索串的个数
listSearch = list(strSearch)
listTotal = list(totalStr)
s = 0
t = 0
existCount = 0
while((s < len(listSearch)) & (t < len(listTotal))):
if(listSearch[s] == listTotal[t]):
if((s + 1) != len(listSearch)):
s+=1
t+=1
else:
existCount+=1
if((len(listTotal) - (t + 1)) >= len(listSearch)):
s = 0
t+=1
else:
break;
elif(s == 0):
s = 0
t+=1
else:
s = s - (s - kmpTable[(s - 1)])
if((t + 1) >= len(listTotal)):
break
#print(existCount)
return existCount
def getKMPtable(strSearch):
#获取kmp的部分匹配数值表
#但得先获取字符串所有可能长度的最大公告元素长度,将其存放到int数组中返回
intTablesLength = len(strSearch)
kmpTable = []
for i in range(intTablesLength):
strItem = strSearch[0 : i + 1]
intMaxPublicNum = getMaxPublicNum(strItem)
kmpTable.append(intMaxPublicNum)
#print(kmpTable)
return kmpTable
def getMaxPublicNum(strItem):
#获取前缀和后缀,并最终对比得到最大的公共元素长度,并返回
intMaxPublicNum = 0
intItemLength = len(strItem)
listFront = []
listBack = []
for i in range(intItemLength - 1):
listFront.append(strItem[0 : i + 1])
for i in range(intItemLength, 1, -1):
listBack.append(strItem[i - 1 : intItemLength])
n = -1
for i in range(intItemLength - 1):
if(listFront[i] == listBack[i]):
n = i
if(n != -1):
intMaxPublicNum = len(listFront[n])
#print(intMaxPublicNum)
return intMaxPublicNum
python
实现的字符串搜索文件和java
实现的字符串搜索文件,其运行速率对比还是很明显,估计问题就在python
对文件编码格式上面,如图
速率相差太大,估计就是代码的问题 java
代码同样也是臃肿…
首发来自公众号: 程序员品
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。