文档章节

看毛片算法 KMP

李雷岗
 李雷岗
发布于 2016/12/07 16:14
字数 442
阅读 9
收藏 0
点赞 0
评论 0

找最长匹配前缀。 

 

 

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()

 

© 著作权归作者所有

共有 人打赏支持
李雷岗
粉丝 2
博文 34
码字总数 22317
作品 0
昌平
高级程序员
「对抗深度强化学习」是如何解决自动驾驶汽车系统中的「安全性」问题的?...

原文来源:arXiv 作者:Aidin Ferdowsi、 Ursula Challita、Walid Saad、Narayan B. Mandayam 「雷克世界」编译:嗯~是阿童木呀、KABUDA 对于自动驾驶汽车(AV)而言,要想在未来的智能交通系...

cf2suds8x8f0v
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
shell脚本在企业中的使用案例(1)--一键式打包

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

baiweibi
06/29
0
0
ffmpeg获取源的pix-fmt

深入代码后,发现是从PPS中得到,最外层的是avformatfindstream_info,如下: 主要介绍decodenalunits,getpixelformat,ffh264decodesliceheader。 static int decodenalunits(H264Context ...

evsqiezi
04/13
0
0
FFMPEG SDK 开发介绍

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

codelive
2012/11/15
0
0
ffmpeg多种码率控制方式的实现

ffmpeg是我们进行视频编解码常用的工具,而对于ffmpeg中编码时对码率的控制方式一直没找合适的教程,无意中在stackoverflow上发现了答案,在此进行总结备忘。 视频编码器常用的码率控制方式包...

tifentan
04/13
0
0
日常运维--rsync同步工具

rsync命令是一个远程数据同步工具,可通过LAN/WAN快速同步多台主机间的文件。rsync使用所谓的“rsync算法”来使本地和远程两个主机之间的文件达到同步,这个算法只传送两个文件的不同部分,而...

chencheng-linux
07/19
0
0
ffmpeg做h264的GPU加速

硬件选择 -hwaccel_device 0 { "hwacceldevice", OPTVIDEO | OPTSTRING | HASARG |OPT_EXPERT | OPTSPEC |OPTINPUT, { .off = OFFSET(hwaccel_devices) }, "select a device for HW accelera......

evsqiezi
04/18
0
0
ffmpeg中设置x264设置sps id,实现多个SPS/PPS

若有这种需求:期望在同一流中存在不同编码参数的h.264流。 应用场景: 视频截取,视频拼接等,可以不进行全部转码了。 核心参数:sps-id 经测试可以通过x264-params或x264opts进行参数设置,...

张旭0512
2015/05/18
0
2
让众多宅男心中的女神们下海不再是梦!

西雅图IT圈:seattleit 【今日作者】宇直 宇宙第一直男 盆友们 你们看毛片吗? 我反正是不看的。 但是最近我听几个朋友说,看自己喜欢的女明星演毛片已经不再是梦了。 我开始是不信的,但是听...

m68futkmurmtj
2017/12/19
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Weblogic问题解决记录

问题:点击登录,页面刷新但是不进去管理界面。解决:删除cookies再登录。

wffger
20分钟前
0
0
RxJava2的错误处理方案

最近使用retrofit2 + rxKotlin2写接口访问,想尽量平铺代码,于是就想到当借口返回的状态码为「不成功」时(比如:code != 200),就连同网络错误一起,统一在onError方法中处理。想法总是好的...

猴亮屏
27分钟前
0
0
程序的调试信息

调试二进制程序时,经常要借助GDB工具,跟踪程序的执行流程,获取程序执行时变量的值,以发现问题所在。GDB能得到这些信息,是因为编译程序时,编译器保存了相应的信息。Linux下的可执行程序...

qlee
50分钟前
0
0
应用级缓存

缓存命中率 从缓存中读取数据的次数与总读取次数的比例,命中率越高越好 java缓存类型 堆缓存 guavaCache Ehcache3.x 没有序列化和反序列化 堆外缓存ehcache3.x 磁盘缓存 存储在磁盘上 分布式...

writeademo
今天
0
0
python爬虫日志(3)find(),find_all()函数

1.一般来说,为了找到BeautifulSoup对象内任何第一个标签入口,使用find()方法。 以上代码是一个生态金字塔的简单展示,为了找到第一生产者,第一消费者或第二消费者,可以使用Beautiful Sou...

茫羽行
今天
0
0
java:thread:顺序执行多条线程

实现方案: 1.调用线程的join方法:阻塞主线程 2.线程池 package com.java.thread.test;public class MyThread01 implements Runnable {@Overridepublic void run() {Syste...

人觉非常君
今天
0
0
ElasticSearch 重写IK分词器源码设置mysql热词更新词库

常用热词词库的配置方式 1.采用IK 内置词库 优点:部署方便,不用额外指定其他词库位置 缺点:分词单一化,不能指定想分词的词条 2.IK 外置静态词库 优点:部署相对方便,可以通过编辑指定文...

键走偏锋
今天
19
0
Git 2.18版本发布:支持Git协议v2,提升性能

Git 2.18版本发布:支持Git协议v2,提升性能Git 2.18版本发布:支持Git协议v2,提升性能 新版本协议的主要驱动力是使 Git 服务端能够对各种 ref(分支与 tag)进行过滤操作。 这就意味着,G...

linux-tao
今天
0
0
python浏览器自动化测试库【2018/7/22-更新】

64位py2.7版本 更新 document_GetResources 枚举页面资源 document_GetresourceText 获取指定url的内容 包括页面图片 下载地址下载地址 密码:upr47x...

开飞色
今天
42
0
关于DCL双重锁失效及解决方案

关于DCL双重锁失效及解决方案 Double Check Lock (DCL)实现单例 DCL 方式实现单例的优点是既能够在需要时才初始化单例,又能够保证线程安全,且单例对象初始化后调用getInstance方法不进行...

DannyCoder
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部