文档章节

看毛片算法 KMP

siri李
 siri李
发布于 2016/12/07 16:14
字数 442
阅读 11
收藏 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()

 

© 著作权归作者所有

共有 人打赏支持
上一篇: 二叉树遍历方法
下一篇: 最小二乘思想
siri李
粉丝 3
博文 34
码字总数 22317
作品 0
昌平
高级程序员
私信 提问
「对抗深度强化学习」是如何解决自动驾驶汽车系统中的「安全性」问题的?...

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

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

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

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
如何在 Linux 系统查询机器最近重启时间

在你的 Linux 或类 UNIX 系统中,你是如何查询系统上次重新启动的日期和时间?怎样显示系统关机的日期和时间? last 命令不仅可以按照时间从近到远的顺序列出该会话的特定用户、终端和主机名...

来来来来来
今天
3
0
Redis协议是什么样的

前言 我们用过很多redis的客户端,有没有相过自己撸一个redis客户端? 其实很简单,基于socket,监听6379端口,解析数据就可以了。 redis协议 解析数据的过程主要依赖于redis的协议了。 我们...

春哥大魔王的博客
今天
6
0
乱入Linux界的我是如何学习的

欢迎来到建哥学Linux,咳!咳!咳!开个玩笑哈,我是一个IT男,IT界的入门选手,正在学习Linux。 在之前,一直想进军IT界,学习IT技术,但是苦于没有人指导,也不知道学什么,最开始我自己在...

linuxCool
今天
4
0
携程Apollo统一配置中心的搭建和使用(java)

一.Apollo配置中心介绍 1、What is Apollo 1.1 Apollo简介 Apollo(阿波罗)是携程框架部门研发的开源配置管理中心,能够集中化管理应用不同环境、不同集群的配置,配置修改后能够实时推送到...

morpheusWB
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部