写在最前面

早在大二我就想写一篇KMP的总结,主要是因为大部分blog上的文章有着各种各样的不足:有的过于冗长,有的学习曲线太陡,而《挑战》和《算法竞赛》上相关部分都因为字符串相关的内容过多,KMP算法部分不甚详尽。但是当时没有发在blog上,因为感觉从next数组谈起的话,算法的推导总会很奇怪、不顺畅。
时隔两年,花了两天时间,重新梳理了逻辑,缀字成文。

KMP算法有什么用

在文本编辑中,我们经常要在一段文本(text)中找到一串我们想要的字符串(即模板,pattern)的位置。由此,便产生了字符串的匹配问题。而KMP就是为高效解决这一问题提出来的。
kmp1

事实上,KMP算法的运行速度和理解的难度都高于其他的单文本单模板匹配算法。但是KMP算法在Tier树上扩展得到的AC自动机算法,是解决单文本多模板匹配的不二法门。如果读者有志于ACM竞赛的话,KMP算法是不能不理解的基础内容。

基础定义

这里简单地定义几个基础的名词,随着推导的深入,新的名词会在文中给出定义。

  • 文本较长,模板较短。我们在文本链上查找模板链。
  • 文本用T表示,长度为n。模板用P表示,长度为m。
  • 文本指针:一个指针
Read the rest

Update 2019/07/26:根据读者提出的问题,添加了查找数据方法、时间安排、论文及代码的下载地址等内容。

前言

本文主要是记录这次建模的过程和思路。用到的模型简单提及,并省略数据和结论。

涉及到的最小二乘法、模糊数学模型和马尔科夫链知识可以见我的文章“半小时学习最小二乘法”“模糊评价模型-以2018美赛为例”“马尔科夫链详解(TBC)”。

问题

Problem: A large multinational service company, with offices in New York City in the United States and Shanghai in China, is continuing to expand to become truly international. This company is investigating opening additional international offices and desires to have the employees of each office speak both in English and one or more additional languages. The Chief Operating Officer of… Read the rest

Update 04.28.2019:重构了本文的逻辑结构,修改了失效的链接

Jupyter Notebook

Jupyter Notebook是一个交互式笔记本,支持运行 40 多种编程语言。它对于希望编写漂亮的交互式文档的人来说是一个强大工具。

划重点: 支持python、交互式文档。

本文的目的是详细地说明Jupyter Notebook安装过程中可能遇到的问题,保证读者在阅读完本文后能够打开在任何目录下、以.ipynb为后缀的任意Jupyter Notebook文件。
具体如何使用Jupyter Notebook,教程见Jupyter Notebook 快速入门
对于代码无法运行,缺少相关库的问题,见“Anaconda/conda使用指南”(TBC)

背景

因为我大一的时候安装了Enthought Canopy(用它的python.exe作为PyCharm内核),所以一直用的是Canopy来打开.ipynb。

但是因为Canopy的Python版本是Python2.7,加上numpy官方宣布某个时间点后不再支持Python2.7,所以打算… Read the rest