## 看毛片算法 KMP 原

siri李

``````import random
import datetime

def BF_Match(s, t):
slen = len(s)
tlen = len(t)
if slen >= tlen:
for k in range(slen - tlen + 1):
i = k
j = 0
while i < slen and j < tlen and s[i] == t[j]:
i = i + 1
j = j + 1
if j == tlen:
return k
else:
continue
return -1

def KMP_Match_1(s, t):
slen = len(s)
tlen = len(t)
if slen >= tlen:
i = 0
j = 0
next_list = [-2 for i in range(len(t))]
getNext_1(t, next_list)
#print next_list
while i < slen:
if j == -1 or s[i] == t[j]:
i = i + 1
j = j + 1
else:
j = next_list[j]
if(j == tlen):
return i - tlen
return -1

def KMP_Match_2(s, t):
slen = len(s)
tlen = len(t)
if slen >= tlen:
i = 0
j = 0
next_list = [-2 for i in range(len(t))]
getNext_2(t, next_list)
#print next_list
while i < slen:
if j == -1 or s[i] == t[j]:
i = i + 1
j = j + 1
else:
j = next_list[j]
if j == tlen:
return i - tlen
return -1

def getNext_1(t, next_list):
next_list[0] = -1
j = 0
k = -1
while j < len(t) - 1:
if k == -1 or t[j] == t[k]:
j = j + 1
k = k + 1
next_list[j] = k
else:
k = next_list[k]

def getNext_2(t, next_list):
next_list[0] = -1
next_list[1] = 0
for i in range(2, len(t)):
tmp = i -1
for j in range(tmp, 0, -1):
if equals(t, i, j):
next_list[i] = j
break
next_list[i] = 0

def equals(s, i, j):
k = 0
m = i - j
while k <= j - 1 and m <= i - 1:
if s[k] == s[m]:
k = k + 1
m = m + 1
else:
return False
return True

def rand_str(length):
str_0 = []
for i in range(length):
str_0.append(random.choice("abcdefghijklmnopqrstuvwxyz"))
return str_0

def main():
x = rand_str(20000)
y = rand_str(5)

print "The String X Length is : ", len(x), " String is :",
for i in range(len(x)):
print x[i],
print ""
print "The String Y Length is : ", len(y), " String is :",
for i in range(len(y)):
print y[i],
print ""

time_1 = datetime.datetime.now()
pos_1 = BF_Match(x, y)
time_2 = datetime.datetime.now()
print "pos_1 = ", pos_1

time_3 = datetime.datetime.now()
pos_2 = KMP_Match_1(x, y)
time_4 = datetime.datetime.now()
print "pos_2 = ", pos_2

time_5 = datetime.datetime.now()
pos_3 = KMP_Match_2(x, y)
time_6 = datetime.datetime.now()
print "pos_3 = ", pos_3

print "Function 1 spend ", time_2 - time_1
print "Function 2 spend ", time_4 - time_3
print "Function 3 spend ", time_6 - time_5

main()
``````

### siri李

「对抗深度强化学习」是如何解决自动驾驶汽车系统中的「安全性」问题的？...

cf2suds8x8f0v
2018/05/08
0
0
JellyBean Camera Service 4.1.2和4.2.1两版本变化

4.2 CameraService的部分代码,和4.1的版本的区别还是比较大的,具体变化多大还没来得及分析.先从他们的代码布局变化看起吧 AndroidJellyBean4.1.2 Camera Service代码布局： frameworks/av/se...

Jerikc
2013/03/09
0
0
ffmpeg获取源的pix-fmt

evsqiezi
2018/04/13
0
0
shell脚本在企业中的使用案例（1）--一键式打包

#!/bin/sh function result() { if [ \$1 -eq 0 ] then echo " \$2..............................................sucess" else echo " \$2..............................................fai......

baiweibi
2018/10/30
0
0
FFMPEG SDK 开发介绍

FFMPEG SDK 开发介绍 1.简介: ffmpeg是一套可以用来记录、转换数字音频、视频，并能将其转化为流的开源计算机程序。 使用ffmpeg能够完成如下功能:parse,demux,decode,filter(preprocessing)...

codelive
2012/11/15
0
0

Nextjs+React非页面组件SSR渲染

@随风溜达的向日葵 Nextjs Nextjs是React生态中非常受欢迎的SSR（server side render——服务端渲染）框架，只需要几个步骤就可以搭建一个支持SSR的工程（_Nextjs_的快速搭建见Next.js入门）...

47分钟前
0
0

3
0
Redis协议是什么样的

6
0

linuxCool

4
0

morpheusWB

3
0