RainAir
My OI Blog
RainAir


文章归档

KMP模板

题目描述 算法介绍 KMP是一种字符串匹配算法,可以求出一个字符串在另一个字符串中出现的次数。 时间复杂度为$ O(N+M) $ 算法实现 算法分为预处理next数组和查询两步进行。 预处理 next数组表示从起始位置到当前位置最长的前缀和后缀的长度 那么,在处理时,我…

   215   2017-11-25 去围观

最短路径模板

图论中的最短路径算法 题目链接 最短路径指的是在一个图里,我们求出某一对点的最短的简单路径。我们有很多算法来解决这个问题。如Floyd,Dijkstra,SPFA等。 Floyd 适用范围 适用于当结点总数很小的时候,能在$ O(n^3) $的时间处理出图中每一对顶点的最短路径。…

   233   2017-11-04 去围观

ST表模板

O(1)求静态区间极值的算法 题目链接 在生活中,总会遇到这样一些题目: 在长度为N的数列中多次查找某区间的最大值。 于是,ST表应运而生 算法描述 ST表是一个可以在* O(nlogn) *的时间复杂度的预处理后,在 * O(1) * 的时间复杂度中查找任意区间的最大值 此算法基…

   1,734   2017-11-03 去围观
文章归档