Logic
向着梦想进发
Logic's Blog

【讲课代码】字符串哈希与KMP

字符串基础

[NOIP 2018 普及组] 字符统计

[NOIP 2011 普及组] 统计单词数

数字反转

CF 1935 A. Entertainment in MAC

CF 1941 C. Rudolf and the Ugly String

字符串哈希

给出一种类STL的哈希实现

[JLOI 2011] 不重复数字

Snowflake Snow Snowflakes

【模板】字符串哈希

字符串匹配

伪代码

最长回文子串

$O(nlogn)$ 做法

$O(n)$ 做法

最长公共子串

智乃的前缀、后缀、回文

前缀函数和KMP算法

【模板】KMP

字符串的周期

最小表示法

本质不同的子串数量

$O(n^2)$ 做法,前缀函数。

汗流浃背了,这个是 copilot 给出的 $O(nlog(n)log(n))$ 做法(然而实际上我并算不来这个复杂度,但是至少这个算法本地可以跑 $n=10^5$)。我被 AI 完爆了,我是说。我还没看懂这个算法,真的。

https://cdn.jsdelivr.net/gh/LogicShao/PicBed/img/%E5%A6%82%E6%9E%9C%E6%98%AF%E8%BF%99%E6%A0%B7%EF%BC%8C%E9%82%A3%E6%88%91%E9%80%80%E7%BD%91.jpg
赞赏
本文作者: Logic
本文链接: https://i.needwe.top/code-for-teaching-string-hash-and-kmp/
本文采用 CC BY-NC-SA 4.0 Unported 协议进行许可

发表回复

textsms
account_circle
email

Logic's Blog

【讲课代码】字符串哈希与KMP
字符串基础 [NOIP 2018 普及组] 字符统计 [crayon-667a31d58899d854602968/] [NOIP 2011 普及组] 统计单词数 [crayon-667a31d5889a2221827651/] 数字反转 [crayon-667a…
扫描二维码继续阅读
2024-04-30