有一个文本串S，和一个模式串P，现在要查找P在S中的位置，怎么查找呢？

假设主串target为: a b a c a a b a c a b a c a b a a b b,模式串pattern: a b a c a b(为了方便查看，每个字符间用空格隔开)。

用暴力算法匹配字符串过程中，我们会把target[0]跟 pattern[0] 匹配，如果相同则匹配下一个字符，直到出现不相同的情况，此时我们会丢弃前面的匹配信息，然后把target[1]跟 pattern[0] 匹配，循环进行，直到主串结束，或者出现匹配成功的情况。这种丢弃前面的匹配信息的方法，极大地降低了匹配效率。

以上面的字符为例子:pattern的前5个字符abaca可以匹配target的前5个字符,但是pattern[5]和target[5]不匹配。下面重新从target[1]开始和pattern匹配。

显然效率很差，因为你要把"搜索位置"移到已经比较过的位置，重比一遍。

上下文无关的组成部分:

• 终结符号
• 非终结符号
• 一个开始符号
• 一组产生式

例如，下面数学表达式:

$$ expr \to expr+term $$

$$ expr \to expr-term $$

$$ expr \to term $$

$$ term \to term * factor $$

$$ term \to term/factor $$

$$ term \to factor $$

$$ factor \to (expr) $$

$$ factor \to id $$

1. 终结符号(词法单元)是组成串的基本符号，例如上面的 +,-。
2. 非终结符号是表示串的集合的语法变量,例如上面的term和factor。非终结符号表示的串集合用于定义由文法生成的语言。

算法之trie字典树

 Trie树，又称字典树、前缀树、单词查找树、键树，是一种多叉树形结构，是一种哈希树的变种。Trie树典型应用是用于快速检索（最长前缀匹配），统计，排序和保存大量的字符串，所以经常被搜索引擎系统用于文本词频统计，搜索提示等场景。它的优点是最大限度地减少无谓的字符串比较，查询效率比较高。

Trie的核心思想是空间换时间，利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

google 提出了 Jump consistent hash 算法，跳转一致性哈希不需要存储，速度更快，并且在均匀划分key方面做得更好。它的主要限制是桶必须按顺序编号，这使得它 比分布式 Web 缓存更适合数据存储应用程序

哈希环法是最常用的、最经典的一致性哈希算法， 也叫做割环法。 这个算法易于理解、应用广泛（例如亚马逊的Dynamo¹）， 实现了最小化的重新映射。

一致性哈希算法是一种特殊的哈希算法， 当目标槽位数量发生变化时，它会尽力降低的重新映射的数量。 传统的哈希表设计中，添加或者删除一个槽位，会造成全量的重新映射， 一致性哈希则追求的是增量式重新映射。

散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使得每个关键字key对应一个存储位置f(key)。査找时，根据这个确定的对应关系找到给定值key的映射f(key),若査找集合中存在这个记录，则必定在f(key)的位置上。

我们把这种对应关系f称为散列函数，又称为哈希(Hash)函数。按这个思想，采用散列技术将记录存储在一块连续的存储空间中，这块连续存储空间称为散列表或哈希表（Hashtable)。那么关键字对应的记录存储位置我们称为散列地址。

给定一个字符串 s，找到 s 中最长的回文子串？

LMAX Disruptor是一个高性能的线程间消息库。下面是其简单架构示意图

之前把ubuntu装到了ssd上，速度变得快了很多。顺手就安装了steam，昨天突然发现磁盘接近满了🤣。立马插上了一块新买的ssd。