boyer-moore算法python

2023-10-24 12:44
文章标签 python 算法 moore boyer

本文主要是介绍boyer-moore算法python,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Boyer-Moore算法是一种用于字符串搜索的高效算法,它通过跳过尽可能多的字符来减少比较的次数。下面是一个简单的Python实现Boyer-Moore算法的示例:

def build_bad_char_table(pattern):

    bad_char_table = {}

    pattern_length = len(pattern)

    for i in range(pattern_length - 1):

        bad_char_table[pattern[i]] = pattern_length - i - 1

    return bad_char_table

def build_good_suffix_table(pattern):

    pattern_length = len(pattern)

    good_suffix_table = [-1] * pattern_length

    last_prefix_position = pattern_length

    for i in range(pattern_length - 1, -1, -1):

        if is_prefix(pattern, i + 1):

            last_prefix_position = i + 1

        good_suffix_table[i] = last_prefix_position + pattern_length - i - 1

    for i in range(pattern_length - 1):

        j = pattern_length - 1 - i

        if is_suffix(pattern, j):

            last_prefix_position = j

        good_suffix_table[j] = min(good_suffix_table[j], pattern_length - 1 - last_prefix_position + j)

    return good_suffix_table

def is_prefix(pattern, p):

    pattern_length = len(pattern)

    j = 0

    for i in range(p, pattern_length):

        if pattern[i] != pattern[j]:

            return False

        j += 1

    return True

def is_suffix(pattern, p):

    pattern_length = len(pattern)

    i = 0

    j = p

    while j < pattern_length:

        if pattern[i] != pattern[j]:

            return False

        i += 1

        j += 1

    return True

def boyer_moore_search(text, pattern):

    bad_char_table = build_bad_char_table(pattern)

    good_suffix_table = build_good_suffix_table(pattern)

    pattern_length = len(pattern)

    text_length = len(text)

    i = 0

    while i <= text_length - pattern_length:

        j = pattern_length - 1

        while j >= 0 and pattern[j] == text[i + j]:

            j -= 1

        if j < 0:

            # Pattern found at index i

            print("Pattern found at index", i)

            i += good_suffix_table[0]

        else:

            # Shift based on the bad character rule and good suffix rule

            bad_char_shift = bad_char_table.get(text[i + j, -1])

            good_suffix_shift = good_suffix_table[j]

            i += max(bad_char_shift, good_suffix_shift)

# 测试Boyer-Moore搜索

text = "This is a sample text for testing the Boyer-Moore algorithm."

pattern = "Boyer-Moore"

boyer_moore_search(text, pattern)

这个示例包含了Boyer-Moore算法的实现,包括构建坏字符表(bad character table)和好后缀表(good suffix table)。然后,boyer_moore_search函数使用这些表来执行搜索。在这个示例中,它会输出找到的模式的索引位置。你可以将text和pattern更改为你自己的文本和模式来测试不同的输入。

这篇关于boyer-moore算法python的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/275246

相关文章

Python将博客内容html导出为Markdown格式

《Python将博客内容html导出为Markdown格式》Python将博客内容html导出为Markdown格式,通过博客url地址抓取文章,分析并提取出文章标题和内容,将内容构建成html,再转... 目录一、为什么要搞?二、准备如何搞?三、说搞咱就搞!抓取文章提取内容构建html转存markdown

Python获取中国节假日数据记录入JSON文件

《Python获取中国节假日数据记录入JSON文件》项目系统内置的日历应用为了提升用户体验,特别设置了在调休日期显示“休”的UI图标功能,那么问题是这些调休数据从哪里来呢?我尝试一种更为智能的方法:P... 目录节假日数据获取存入jsON文件节假日数据读取封装完整代码项目系统内置的日历应用为了提升用户体验,

Python FastAPI+Celery+RabbitMQ实现分布式图片水印处理系统

《PythonFastAPI+Celery+RabbitMQ实现分布式图片水印处理系统》这篇文章主要为大家详细介绍了PythonFastAPI如何结合Celery以及RabbitMQ实现简单的分布式... 实现思路FastAPI 服务器Celery 任务队列RabbitMQ 作为消息代理定时任务处理完整

Python Websockets库的使用指南

《PythonWebsockets库的使用指南》pythonwebsockets库是一个用于创建WebSocket服务器和客户端的Python库,它提供了一种简单的方式来实现实时通信,支持异步和同步... 目录一、WebSocket 简介二、python 的 websockets 库安装三、完整代码示例1.

揭秘Python Socket网络编程的7种硬核用法

《揭秘PythonSocket网络编程的7种硬核用法》Socket不仅能做聊天室,还能干一大堆硬核操作,这篇文章就带大家看看Python网络编程的7种超实用玩法,感兴趣的小伙伴可以跟随小编一起... 目录1.端口扫描器:探测开放端口2.简易 HTTP 服务器:10 秒搭个网页3.局域网游戏:多人联机对战4.

使用Python实现快速搭建本地HTTP服务器

《使用Python实现快速搭建本地HTTP服务器》:本文主要介绍如何使用Python快速搭建本地HTTP服务器,轻松实现一键HTTP文件共享,同时结合二维码技术,让访问更简单,感兴趣的小伙伴可以了... 目录1. 概述2. 快速搭建 HTTP 文件共享服务2.1 核心思路2.2 代码实现2.3 代码解读3.

Python使用自带的base64库进行base64编码和解码

《Python使用自带的base64库进行base64编码和解码》在Python中,处理数据的编码和解码是数据传输和存储中非常普遍的需求,其中,Base64是一种常用的编码方案,本文我将详细介绍如何使... 目录引言使用python的base64库进行编码和解码编码函数解码函数Base64编码的应用场景注意

Python基于wxPython和FFmpeg开发一个视频标签工具

《Python基于wxPython和FFmpeg开发一个视频标签工具》在当今数字媒体时代,视频内容的管理和标记变得越来越重要,无论是研究人员需要对实验视频进行时间点标记,还是个人用户希望对家庭视频进行... 目录引言1. 应用概述2. 技术栈分析2.1 核心库和模块2.2 wxpython作为GUI选择的优

Python如何使用__slots__实现节省内存和性能优化

《Python如何使用__slots__实现节省内存和性能优化》你有想过,一个小小的__slots__能让你的Python类内存消耗直接减半吗,没错,今天咱们要聊的就是这个让人眼前一亮的技巧,感兴趣的... 目录背景:内存吃得满满的类__slots__:你的内存管理小助手举个大概的例子:看看效果如何?1.

Python+PyQt5实现多屏幕协同播放功能

《Python+PyQt5实现多屏幕协同播放功能》在现代会议展示、数字广告、展览展示等场景中,多屏幕协同播放已成为刚需,下面我们就来看看如何利用Python和PyQt5开发一套功能强大的跨屏播控系统吧... 目录一、项目概述:突破传统播放限制二、核心技术解析2.1 多屏管理机制2.2 播放引擎设计2.3 专