字符串
排序
- 低位优先排序
public static void sort(String[]a,int W) { int N = a.length; int R = 256; String[] aux = new String[N]; //循环W次键索引记数法 for(int d = W-1; d>=0;d--) { int[] count = new int[R+1]; //键索引记数法第一步--频率统计 for(int i=0;i<N;i++) count[a[i].charAt(d)+1]++; //键索引记数法第二步--将频率转化为索引 for(int r=0;r<R;r++) count[r+1]+=count[r]; //键索引记数法第三步--排序 for(int i=0;i<N;i++) aux[count[a[i].charAt(d)]++] = a[i]; //键索引记数法第四步--回写 for(int i=0;i<N;i++) a[i]=aux[i]; }}- 高位优先排序
public class MSD { private static int R = 256; //字符串中最多可能出现的字符的数量 private static final int M = 15; //当子字符串长度小于M时，用直接插入排序 private static String[] aux; //辅助数组 //实现自己的chatAt()方法 private static int charAt(String s, int d) { if(d<s.length())return s.charAt(d); else return -1; } public static void sort(String[] a) { int N = a.length; aux = new String[N]; sort(a,0,N-1,0); } private static void sort(String[] a,int lo, int hi, int d) { if(hi<=lo+M) {Insertion.sort(a,lo,hi,d);return;} //切换为直接插入排序 int[] count = new int[R+2]; //键索引记数法第一步 for(int i=lo; i<=hi;i++) count[charAt(a[i],d)+2]++; //键索引记数法第二步 for(int r=0;r<R+1;r++) count[r+1]+=count[r]; //键索引记数法第三步 for(int i=lo;i<=hi;i++) aux[count[a[i].charAt(d)+1]++] = a[i]; //键索引记数法第四步 for(int i=lo;i<=hi;i++) a[i]=aux[i-lo]; //递归以每个字符为键进行排序 for(int r=0;r<R;r++) sort(a,lo+count[r],lo+count[r+1]-1,d+1); }}- 三向字符串快速排序
public class Quick3string { private static int charAt(String s, int d) { if(d<s.length())return s.charAt(d); else return -1; } public static void sort(String[] a) { sort(a,0,a.length-1,0); } public static void sort(String[] a,int lo, int hi, int d) { if(hi<=lo) return; int lt = lo, gt = hi; int v = charAt(a[lo], d); int i = lo+1; while(i<=gt) { int t = charAt(a[lo],d); if(t<v) exch(a,lt++,i++); else if(t>v) exch(a,i,gt--); else i++; } sort(a,lo,lt-1,d); if(v>=0) sort(a,lt,gt,d+1); sort(a,gt+1,hi,d); }}单词查找树
trie 树存储的开销要小得多，并且因为它天然的前缀匹配和排序的特性，在很多时候也能更快检索数据
trie 树的本质就是利用字符串之间的公共前缀，将重复的前缀合并在一起
单次查找树是一种多模式串的字符匹配算法
stateDiagram-v2 g --> o o --> l l --> d l --> a a --> n n --> s查找
插入
查询所有键
- 通过递归的方式，如果有分叉，则生成一个由pre+branch的新字符串
public Interable<String> keys() { return keysWithPrefix("");}public Interable<String> keysWithPrefix(String pre) { Queue<String> q = new Queue<String>(); collect(get(root, pre, 0), pre, q); return q;}private void collect(Node x, String pre, Queue<String> q) { if (x == null) return; if (x.val != null) q.enqueue(pre); for (char c = 0; c < R; c++) collect(x.next[c], pre + c, q);}- 删除
找到键所对应的结点并将它的值设为空（null）。如果该结点含有一个非空的链接指向某个子结点，那么就不需要在进行其他操作了。如果它的所有链接均为空，那就需要在数据结构中删去这个结点。如果删去它使得它的父结点的所有链接也均为空，就需要继续删除它的父结点，以此类推
public void delete(String key) { root = delete (root, key, 0);}private Node delete(Node x, String key, int d) { if (x == null) return null; if (d == key.length()) x.val = null; else { char c = key.charAt(d); x.next[c] = delete(x.next[c], key, d+1); } if (x.val != null) return x; for (char c = 0; c < R; c++) if (x.next[c] != null) return x; return null;}- 优化
为了解决内存消耗的问题，有一种称之为缩点优化的手段，就是对只有一个子节点的节点，而且此节点不是一个串的结束节点，可以将此节点与子节点合并
stateDiagram-v2 g --> o o --> l l --> d l --> ans三向单词查找树
在三向单词查找树（TST）中，每个结点都含有一个字符、三条链接和一个值。这三条链接分别对应着当前字母小于、等于和大于结点字母的所有键
子字符串查找
暴力查找
public static int search(String pat, String txt) { int M = pat.length(); int N = txt.length(); // 逐个位置匹配模式字符串 for (int i = 0; i < N; i++) { int j; for (j = 0; j < M; j++) { if (txt.charAt(i + j) != pat.charAt(j)) { break; } } // 找到了匹配的字符串 if (j == M) { return i; } } return N; }这种算法的最坏情况时间复杂度是 O(n*m)
暴力查找(显式回退)
public static int searchother(String pat, String txt) { int M = pat.length(); int N = txt.length(); int i; int j; // 逐个位置匹配模式字符串 for (i = 0, j = 0; i < N && j < M; i++) { if (txt.charAt(i) == pat.charAt(j)) { j++; } else { i -= j; j = 0; } } // 找到了匹配的字符串 if (j == M) { return i - M; } else { return N; } }RK算法
通过哈希算法对主串中的 n-m+1 个子串分别求哈希值，然后逐个与模式串的哈希值比较。如果某个子串的哈希值与模式串相等，那就说明对应的子串和模式串匹配了
为了提高效率，需要特别设计哈希算法，相邻两个子串的哈希值的计算公式有一定关系，只需要扫描一遍主串就能计算出所有子串的哈希值了
b a d d e fb a d d => [h1, h2, h3, h4] => H1 a d d e => [h2, h3, h4 , h5] => H2 d d e f => [h3, h4, h5, h6] => H3由于哈希冲突的存在，当哈希相同时，还要去比较子串是否匹配模式串。如果存在大量的冲突，每次都要再对比子串和模式串本身，那时间复杂度就会退化成 O(n*m)
KMP算法
KMP 算法的整体思想跟 BM 算法一样，通过构建一个 next 数组，当发现模式串不匹配时，尽量地多往后移动，降低匹配次数
BM算法
BM 算法核心思想是，利用模式串本身的特点，在模式串中某个字符与主串不能匹配的时候，将模式串往后多滑动几位，以此来减少不必要的字符比较，提高匹配的效率
BM 算法在最好情况下的时间复杂度非常低，是 O(n/m)
坏字符规则（Bad Character Rule）： 当发现不匹配的字符时，算法会将模式串向右移动，使得模式串中的字符与目标串中的字符对齐，以最大化跳过的比较次数。为了实现这一点，BM 算法会预先计算每个字符在模式串中的最右出现位置，并根据目标串中的字符在模式串中的位置进行调整。
好后缀规则（Good Suffix Rule）： 当匹配失败时，算法会尽量将模式串向右滑动，以使得模式串的某个后缀能够与目标串中的已匹配部分相匹配。这需要事先计算模式串中每个后缀与目标串中的已匹配部分相匹配的最大长度
RK指纹字符查找算法
AC自动机
AC 自动机实际上就是在 Trie 树之上，加了类似 KMP 的 next 数组
正则表达式
- 连接
AB -> {AB}
- 或
Ａ|B -> {A,B}
- 闭包
Ｂ* -> 0个或多个Ｂ
构造正则表达式
数据压缩
游程编码
行程编码（Run Length Encoding，RLE), 又称游程编码、行程长度编码、变动长度编码 等，是一种统计编码。主要技术是检测重复的比特或字符序列，并用它们的出现次数取而代之
哈夫曼编码
用较少的比特表示出现次数多的字符，用较多的比特表示出现频率低的字符，不同的字符编码间不能彼此成为对方的前缀
- 使用单词查找树实现
使用变长前缀，用一棵二叉树来标记每个字符的编码方式，左分支代表 0、右分支代表 1，所有需要编码的字符都对应二叉树的叶子节点，根结点到该叶子结点的路径就代表着该字符的编码方式
LZW压缩
LZW编码 (Encoding) 的核心思想其实比较简单，就是把出现过的字符串映射到记号上，这样就可能用较短的编码来表示长的字符串，实现压缩
LZW的一个核心思想，即压缩后的编码是自解释 (self-explaining) 的。什么意思？即字典是不会被写进压缩文件的，在解压缩的时候，一开始字典里除了默认的0->A和1->B之外并没有其它映射，2->AB是在解压缩的过程中一边加入的。这就要求压缩后的数据自己能告诉解码器，完整的字典，例如2->AB是如何生成的，在解码的过程中还原出编码时用的字典