文档章节

看毛片算法 KMP

李雷岗
 李雷岗
发布于 2016/12/07 16:14
字数 442
阅读 10
收藏 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
ffmpeg获取源的pix-fmt

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

evsqiezi
04/13
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 SDK 开发介绍

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

codelive
2012/11/15
0
0

没有更多内容

加载失败,请刷新页面

加载更多

原型模式

1、原型模式-定义 用原型实例指定创建对象的种类,并且通过拷贝这些原型创建新的对象 克隆(浅度克隆->拷贝值类型或者引用,深度克隆->创建新的对象,开辟新的内存) 例如客户端知道抽象Pro...

阿元
今天
47
0
awk命令扩展使用操作

awk 中使用外部shell变量 示例1 [root@centos01 t1022]# A=888[root@centos01 t1022]# echo "" | awk -v GET_A=$A '{print GET_A}'888[root@centos01 t1022]# echo "aaaaaaaaaaaaa" | aw......

野雪球
今天
41
0
深入解析MySQL视图VIEW

Q:什么是视图?视图是干什么用的? A:视图(view)是一种虚拟存在的表,是一个逻辑表,本身并不包含数据。作为一个select语句保存在数据字典中的。   通过视图,可以展现基表的部分数据;...

IT--小哥
今天
45
0
虚拟机学习之二:垃圾收集器和内存分配策略

1.对象是否可回收 1.1引用计数算法 引用计数算法:给对象中添加一个引用计数器,每当有一个地方引用它时,计数器值就加1;当引用失效时,计数器值就减1;任何时候计数器值为0的对象就是不可能...

贾峰uk
今天
40
0
smart-doc功能使用介绍

smart-doc从8月份底开始开源发布到目前为止已经迭代了几个版本。在这里非常感谢那些敢于用smart-doc去做尝试并积极提出建议的社区用户。因此决定在本博客中重要说明下smart-doc的功能,包括使...

上官胡闹
昨天
47
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部