MENU

KMP算法(1):如何理解KMP

系列文章目录

KMP 算法(1):如何理解 KMP
KMP算法(2):其细微之处

一:背景

给定一个主串(以 S 代替)和模式串(以 P 代替),要求找出 P 在 S 中出现的位置,此即串的模式匹配问题。

Knuth-Morris-Pratt 算法(简称 KMP)是解决这一问题的常用算法之一,这个算法是由高德纳(Donald Ervin Knuth)和沃恩·普拉特在1974年构思,同年詹姆斯·H·莫里斯也独立地设计出该算法,最终三人于1977年联合发表。

在继续下面的内容之前,有必要在这里介绍下两个概念:真前缀真后缀

由上图所得, "真前缀"指除了自身以外,一个字符串的全部头部组合;"真后缀"指除了自身以外,一个字符串的全部尾部组合。(网上很多博客,应该说是几乎所有的博客,也包括我以前写的,都是“前缀”。严格来说,“真前缀”和“前缀”是不同的,既然不同,还是不要混为一谈的好!)

阅读全文

Manacher算法

一:背景

给定一个字符串,求出其最长回文子串。例如:
(1):s="abcd",最长回文长度为 1;
(2):s="ababa",最长回文长度为 5;
(3):s="abccb",最长回文长度为 4,即bccb。

以上问题的传统思路大概是,遍历每一个字符,以该字符为中心向两边查找。其时间复杂度为$O(n^2)$,效率很差。

1975年,一个叫Manacher的人发明了一个算法,Manacher算法(中文名:马拉车算法),该算法可以把时间复杂度提升到$O(n)$。下面来看看马拉车算法是如何工作的。

阅读全文

表达式求值

一:前言

所谓表达式求值,就是写一个微型计算器。例如输入:(1+9)* 2 / 2 - 1,输出计算结果9。对于这样的问题,我们一般利用栈,模拟数学运算来完成。为了简化问题,在继续下面的分析之前,先在此作个约定:本文只讨论+-*/()基本的四则运算,另外不对意外出现的符号(例如^)和不符合规范的数学表达式(例如2*-1)做异常处理。

阅读全文

单链表的各种操作(面试必备)

一:前言

单链表经常为公司面试所提及,先不贬其过于简单,因为单链表确实是数据结构中最简单的一部分,但往往最简单的,人们越无法把握其细节。本文一共总结了单链表常被提及的各种操作,如下:
(1)逆序构造单链表;
(2)链表反转;
(3)链表排序;
(4)合并两个有序链表;
(5)求出链表倒数第k个值;
(6)判断链表是否有环,有环返回相遇结点;
(7)在一个有环链表中找到环的入口;
(8)删除当前结点;
(9)找出链表的中间结点。

阅读全文

算法复杂度分析概要

一:渐近符号

1.1 符号的辨析

1.1.1 符号$O$

$O$,读作“大O”,非正式来说,$O(g(n))$是增长次数小于等于$g(n)$及其常数倍($n$趋向于无穷大)的函数集合。

定义 如果函数$f(n)$包含在$O(g(n))$中,记作$f(n)∈O(g(n))$(平时使用为了方便书写,我们通常使用$f(n)=O(g(n))$代替)。它的成立条件是:对于所有足够大的$n$,$f(n)$的上界由$g(n)$的常数倍所确定,也就是说,存在大于$0$的常数$c$和非负整数$n_0$,使得对于所有的$n≥n_0$来说,$f(n)≤c⋅g(n)$。

下图说明了这个定义:

阅读全文

BFPRT算法(TOP-K问题)

一:背景介绍

在一堆数中求其前k大或前k小的问题,简称TOP-K问题。而目前解决TOP-K问题最有效的算法即是"BFPRT算法",又称为"中位数的中位数算法",该算法由Blum、Floyd、Pratt、Rivest、Tarjan提出,最坏时间复杂度为$O(n)$。

在首次接触TOP-K问题时,我们的第一反应就是可以先对所有数据进行一次排序,然后取其前k即可,但是这么做有两个问题:

  • 快速排序的平均复杂度为$O(nlogn)$,但最坏时间复杂度为$O(n^2)$,不能始终保证较好的复杂度。

  • 我们只需要前k大的,而对其余不需要的数也进行了排序,浪费了大量排序时间。

除这种方法之外,堆排序也是一个比较好的选择,可以维护一个大小为k的堆,时间复杂度为$O(nlogk)$。

那是否还存在更有效的方法呢?BFPRT算法的做法就是在快速排序的基础上,通过判断主元位置与k的大小使递归的规模变小,其次通过修改快速排序中主元的选取方法来降低快速排序在最坏情况下的时间复杂度

下面先来简单回顾下快速排序的过程,以升序为例:

(1):选取主元(数组中随机一个元素);
(2):以选取的主元为分界点,把小于主元的放在左边,大于主元的放在右边;
(3):分别对左边和右边进行递归,重复上述过程。

阅读全文