两个字符串算法

第一个是最大公共子序列,使用的是动态规划的技术

str1 = 'GTACCGTCA'
str2 = 'CATCGA'
def LCS_table(str1, str2):

"""

这部分主要使用了动态规划的技术,就是如果两个最大公共子序列相等的话,必然前面的也相等

"""

    str_length1 = len(str1)
    str_length2 = len(str2)
    lcs_table = [ [0 for j in range(str_length2 + 1)] for i in range(str_length1 + 1)]
    print(lcs_table)
    for index1,char1 in enumerate(str1):
        i = index1 + 1
        for index2,char2 in enumerate(str2):
            j = index2 + 1
            print(i,j)
            if char1 == char2:
                    lcs_table[i][j] = lcs_table[i-1][j-1] + 1
            else:                   
                lcs_table[i][j] = max(lcs_table[i][j-1], lcs_table[i-1][j])  
    return lcs_table

"""

这个是KMP算法,首先求出next_table,这里记录着要偏移的位数,通过这个减少判断量

"""

pattern = 'ABCDABD'
text = 'BBC ABCDAB ABCDABCDABDE'
def prefix(string):

"""

用于求前缀的函数

"""

    prefix_set = set()
    length = len(string)
    if length == 1:
        return prefix_set
    for i in range(length):
        substring = string[:i]
        prefix_set.add(substring)
    prefix_set.remove('')
    return prefix_set
def suffiex(string):

"""

求后缀的函数

"""

    suffiex_set = set()
    length = len(string)
    for i in range(length):
        substring = string[i + 1:length]
        suffiex_set.add(substring)
    suffiex_set.remove('')
    return suffiex_set        
def next_table(string):

"""

求前缀和后缀的并集最大长度的长度,与对应的字符放在一块,这个就是部分匹配值

"""

    next_state_table = []
    for index,char in enumerate(string):
        strd = index + 1
        substring = string[:strd]
        p_set = prefix(substring)
        s_set = suffiex(substring)
        interset = p_set & s_set
        if interset:
            interset_number = len(max(interset))
        else:
            interset_number = 0
        next_state_table.append(interset_number)
    return next_state_table
def KMP(pattern,text):

"""

"""

    offset = 0#偏移位数
    number = 0#模式的第几位
    next_state = next_table(pattern)
    for char in text:
        if offset != 0:#用于跳转
            offset -= 1
            continue
        if number == 7:#说明都匹配上了
            print('success')
            break
        if char == pattern[number]:
            number += 1
            continue#这样可以一直匹配到不匹配
        if char != pattern[number] and number != 0:
            offset = (number) - next_state[number - 1]
            number = 0

原文发布于微信公众号 - 鸿的学习笔记(shujuxuexizhilu)

原文发表时间:2017-07-28

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏编舟记

泛型编程

泛型编程是一种编程风格,其中算法以尽可能抽象的方式编写,而不依赖于将在其上执行这些算法的数据形式。

802
来自专栏大数据风控

Python中字段抽取、字段拆分、记录抽取

1、字段抽取 字段抽取是根据已知列数据的开始和结束位置,抽取出新的列 字段截取函数:slice(start,stop) 注意:和数据结构的访问方式一样,开始位置...

2578
来自专栏程序员叨叨叨

5.3 结构类型

Cg 语言支持结构体(structure),实际上 Cg 中的结构体的声明、使用和 C++ 非常类似(只是类似,不是相同)。一个结构体相当于一种数据类型,可以定...

592
来自专栏HTML5学堂

原生JS | 当兔子遇到鸡

HTML5学堂-码匠:当兔子遇到鸡,会怎样呢?先别急,看个小视频~ 视频内容 当兔子遇到鸡 —— 不要害怕和别人不一样,在这个世界上,你就是独一无二的自己! 不...

44410
来自专栏HTML5学堂

算法之旅 | 选择排序法

HTML5学堂-码匠:数据快速的计算与排序,与前端页面性能有直接的关系。由于排序的算法有很多,在本次“算法系列”的分享当中,我们先从简单易上手的选择排序法开始,...

3275
来自专栏Golang语言社区

深入解析快速排序算法的原理及其Go语言版实现

快速排序是一种基于分治技术的重要排序算法。不像归并排序是按照元素在数组中的位置对它们进行划分,快速排序按照元素的值对它们进行划分。具体来说,它对给定数组中的元素...

3375
来自专栏数据结构与算法

P1168 中位数

题目描述 给出一个长度为N的非负整数序列A[i],对于所有 ]的中位数。 个数的中位数。 输入输出格式 输入格式: 输入文件median.in的第1...

31511
来自专栏数据结构与算法

1083 Cantor表

题目描述 Description 现代数学的著名证明之一是Georg Cantor证明了有理数是可枚举的。他是用下面这一张表来证明这一命题的: 1/1 1/2 ...

3117
来自专栏编程

Python内置函数int高级用法

int()函数常用来把其他类型转换为整数,例如: >>>int(3.2) 3 >>>int(1/3) 其实,int是Python内置类型之一,之所以能够当作函数...

2529
来自专栏算法channel

常用排序算法代码兑现

主要推送关于对算法的思考以及应用的消息。坚信学会如何思考一个算法比单纯地掌握100个知识点重要100倍。本着严谨和准确的态度,目标是撰写实用和启发性的文章,欢迎...

35311

扫码关注云+社区