字符串模式匹配算法简析（2）—— Rabin Karp 算法

前情提要 之前写过一篇：https://www.kmahyyg.xyz/archives/105 简要介绍了大学课本中常见的 KMP 和 BruteForce 子字符串模式匹配算法，同时根据 WikiPedia 的内容扩展了 Sunday 算法。 今天在完成 LeetCode 的过程中 https://leetcode.com/problems/implement-strstr 发现 builtin 的 strings 的库速度最快，引起了我的好奇。 本科阶段几乎都学过 KMP 算法，然而 KMP 算法的 next 数组的生成难于理解，生成算法也不是很方便，没有通用性、记忆的性价比也不够高。不论是实际应用还是面试，我想都不是一个好的选择。 常见的几个语言中： Java String 类中的 indexOf() 方法，C++ 的 strstr() 函数，使用了 O(n*m) 的暴力比较；Golang strings 包中的 Index() 方法中使用了下述 Rabin-Karp 算法，时间复杂度 O(n+m)，同样没有使用 KMP。Golang 使用 R-K 配合上其对 Bytes 序列的优化，达成了较好的运算速度。 Rabin Karp 依赖 ——... » read more

0
Read
kmahyyg
pb-go: 又一个使用 Golang 编写的 PasteBin 服务

前言 作者按：假期中闲来无事，想把 Golang 学习一下。 趁着疫情导致的“加长版”假期，编写了一个自己的 Pastebin 服务，对标 ptpb/pb 这套服务（公开实例： https://fars.ee ），之前自己也架设过一套这类服务，这套服务易用，但是没有任何的清理和防滥用机制，Python 编写也导致性能奇差。而我是一个注重隐私和安全的人，希望能够自己掌控自己的数据，同时向公众提供高效可靠的服务。 我曾经还架设过 fiche (公开实例： https://termbin.com )，这个用 c 编写的纯 Socket Pastebin，虽然好用，但是没有办法抵挡住任何的 Bot，且会产生大量的磁盘碎片。也没有代码高亮功能。 Golang 编写的程序具有原生交叉编译和单二进制文件的特性，同时也兼具了编译语言相对解释语言的高效，同时门槛较低。在实现这个产品的过程中，得到了 STRRL 的支持，非常感谢。这个产品的实践也让我加深了对 OOP 的理解和软件工程设计、流程、项目协作的了解，也踩了一些新手容易踩的 Golang 的坑，积累了一定的经验。 产品特性（EN） 服务地址 公共实例：https://pbgo.top 项目开源地址：https://github.com/pb-go/pb-go 如果您喜欢的话，不妨给我个 Star，谢谢。我们也欢迎您在使用过程中对我们的项目提出宝贵的意见和建议。项目 Readme 页面有我们的交流群地址，项目 Issue 也同时为您开放。

0
Read
kmahyyg
一个简单的 Telegram Bot 开发实践

Acknowledge A huge thank to @BennyThink . He helps me solved a lot of problems. https://blog.nfz.moe/archives/how-to-write-beautiful-github-readme.html https://github.com/BennyThink/ExpressBot http://drakeet.me/create-telegram-bot-with-python/ https://www.stackoverflow.com Thanks for those experts. https://www.liaoxuefeng.com Thanks for his tutorials. Very useful for green hands. https://github.com/eternnoir/pyTelegramBotAPI Thanks for dependencies. https://github.com/coderfox/Kuaidi100API Thanks for dependencies. https://fast.v2ex.com/member/showfom and his https://ip.sb https://sm.ms https://u.nu https://core.telegram.org/bots/api Start up from Lifehacker Originally, when I... » read more

0
Read
kmahyyg
Python 3 中对递归函数及其经典示例的思考

递归 与 尾递归 递归是一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。 如果一个函数中所有递归形式的调用都出现在函数的末尾，我们称这个递归函数是尾递归的。当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时，这个递归调用就是尾递归。尾递归函数的特点是在回归过程中不用做任何操作，这个特性很重要，因为大多数现代的编译器会利用这种特点自动生成优化的代码。 递归算法的应用 递归算法，在很大程度上减少了代码量，尽可能减少了使用循环时重复判定带来的逻辑不清与出现错误的可能性，可以帮助程序员更专注于思维和程序功能的实验，而并非冗杂的语法逻辑转换。尾递归则在递归算法的基础上进一步优化，在返回时不再涉及运算式，尽可能能地调用原函数代码，利用这个特性，可以提高堆栈利用率，减少出现堆栈溢出的可能。 以Python3为例，下同，我们定义一个阶乘函数。 当你输入fact1(100)可能不会有差别，然而当你输入fact1(998)的时候，你就会得到下面的提示（Python本身的限制是1000，这个溢出的界限取决于机器，我的服务器就可以执行fact1(999)，我的笔记本就不行）： 实际上，我们可以通过写成尾递归的形式对其进行优化： 解决递归调用栈溢出的方法是通过尾递归优化，事实上尾递归和循环的效果是一样的，所以，把循环看成是一种特殊的尾递归函数也是可以的。 尾递归是指，在函数返回的时候，调用自身本身，并且，return语句不能包含表达式。这样，编译器或者解释器就可以把尾递归做优化，使递归本身无论调用多少次，都只占用一个栈帧，不会出现栈溢出的情况。 上面的fact(n)函数由于return n * fact(n – 1)引入了乘法表达式，所以就不是尾递归了。要改成尾递归方式，需要多一点代码，主要是要把每一步的乘积传入到递归函数中。 然而，不幸的是，仅有少部分高级语言的解释器对尾递归进行了优化，对于Python3和绝大多数语言解释器而言，尾递归是没有任何优化的。 尽管如此，为了使你的代码具有更高的资源利用率，我还是建议你写成尾递归的形式。

0
Read
kmahyyg
C 语言关于数组和链表的一些想法

数组和链表 https://www.cnblogs.com/tao560532/articles/2199280.html 一图流，与我交流可以使用评论框或页面底部任意方式。 踩坑笔记 Define a string var using char. In C , string var is not like the python. You have to declare it first , then make a pointer to the exact string. Ref1 : https://stackoverflow.com/questions/8732325/how-to-declare-strings-in-c Ref2 : https://stackoverflow.com/questions/4337217/difference-between-signed-unsigned-char Ref3 : https://stackoverflow.com/questions/3862842/difference-between-char-str-string-and-char-str-string At the end of each string , the system will add... » read more

0
Read
kmahyyg
关于 C 的 CRC32 实现

CRC32 是数据包校验的一个重要算法，本文主要记录作者的一些思考。 Preface 最近讲了计算机网络课程，在上课过程中明白了 CRC32 的人工计算方法。个人猜测后面计算机网络实验会做，趁最近忙碌，一鼓作气，在刚刚学完的时候一起实现了吧。 关于 CRC32 具体的原理性的东西就不说了，大家自己搜索 IEEE 802.3 相关文档和维基百科吧。主要用途是传输过程中的错误检测，由于容错率高，简单易于实现，占用资源少，得到了广泛的应用。 关于 手动计算 就那点内容，其实我也很懵逼，就多查查资料吧。剩下的就是 Talk is cheap, show me the code! ，大家自己根据 Reversed CRC32 的 GZip 实现参考吧。 参考文献 https://www.xilinx.com/support/documentation/application_notes/xapp209.pdf

0
Read
kmahyyg
KMP 与 BF 字符串模式匹配算法简析

字符串模式匹配算法 这里讨论两种常见的字符串模式匹配算法，不讨论字符串的预处理。 关于对字符串进行搜索，请参考 Boyer-Moore 字符串搜索算法 (Wikipedia CN) 另外建议大家阅读 [Sunday 算法] BF 算法 (Brute Force) 返回子串 Ptn 在主串 Tag 的第 pos 个字符后(含第 pos 个位置)第一次出现的位置，若不存在，则返回 -1，这里的位置全部以从 0 开始计算为准，其中 T 非空，0 <= pos <= Tlen。 使用 i 标记当前在 Tag 中匹配的字符的位置，初始值为 pos。 使用 j 标记 Ptn 中正在等待比较的位置，初始值为 0,下同。 即对 Tag 的每一个字符与 Ptn 的字符进行逐字比较： 若完整匹配则返回匹配成功的 pos 值。 匹配过程中，对当前的 pos 值对应位置之后的每一字符进行... » read more

0
Read
kmahyyg