Trie树

基本介绍

Trie树,又称单词查找树,字典树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较,查询效率比哈希树高。

阅读更多...

The begin

这个博客是某位大佬帮我写的,以后会放上友情链接(现在还不会。。。

开这个博客,时不时会上传一下我写过的题目的一些题解,加深一下印象,记录一下我这个菜鸡的ACM学习历程。

这应该也是我博客生涯的开始吧。

1
cout << "Hello World" << endl ;

KMP算法

算法介绍

KMP 算法是 D.E.Knuth、J,H,Morris 和 V.R.Pratt 三位神人共同提出的,称之为 Knuth-Morria-Pratt 算法,简称 KMP 算法。该算法相对于 Brute-Force(暴力)算法有比较大的改进,主要是消除了主串指针的回溯,从而使算法效率有了某种程度的提高。

使用KMP算法能够快速的找到目标串中的模式串。

时间复杂度为$O(m+n)$。

阅读更多...

HDU-3631 Shortest Path 题解

题目大意

给你一张加权有向多重图,你可以对这张图进行两种操作

(1)在图中标记一个顶点。
(2)仅通过标记的顶点找到两个顶点之间的最短路径。

对于操作“ 0 x”,表示标记x点,如果点x已经被标记了,则输出“ ERROR! At point x“。

对于操作“ 1 x y”,如果未标记点x或点y,则输出“ERROR! At path x to y”;

如果无法通过标记顶点从x到达y,则输出“No such path”;

否则,输出最短路径的长度。

在两个连续的测试用例之间有一个空白行。

阅读更多...
  • © 2015-2021 sakurakarma
  • Powered by Hexo Theme Ayer
  • PV: UV:

请我喝杯咖啡吧~

支付宝
微信