排序
排序算法类模板：
public class Sort {
@SuppressWarnings("unchecked")
private static boolean less(Comparable v, Comparable w) {
return (v.compareTo(w) < 0);
}
private static void exch(Object[] a, int i, int j) {
Object swap = a[i];
a[i] = a[j];
a[j] = swap;
}
private static void show(Comparable[] a) {
for (int i = 0; i < a.length; i++) {
System.out.print(a[i]);
}
}
public static void sort(Comparable[] a) {
// 具体实现
}
public static void main(String[] args) {
String[] a =
{"E","F","G","A","B","Q","R","S","T","U","V","W","X","D","H","I","J","K","L","M","C","O","P","N","Y","Z","X","X"};
Sort.sort(a);
show(a);
}
}
选择排序
首先找到数组中最小的那个元素，然后将它和数组的第一个元素交换位置（如果第一个元素就是最小元素，那么它就和自己交换位置）。在剩下的元素中找到最小的元素，将它与数组的第二个元素交换位置，如此往复，直到将整个数组排序。
public static void selectionSort(Comparable[] a) {
int N = a.length;
for (int i = 0; i < N; i++) {
int min = i;
for (int j = i+1; j < N; j++) {
if (less(a[j], a[min])) min = j;
}
exch(a, i, min);
}
}
插入排序
每次选择最小的一个元素插入到已排序序列中。
public static void insertSort(Comparable[] a) {
int N = a.length;
for (int i = 0; i < N; i++) {
for (int j = i; j > 0 && less(a[j], a[j-1]); j--) {
exch(a, j, j-1);
}
}
}
插入排序不会访问索引右侧的元素，选择排序不会访问索引左侧的元素。 插入排序对于部分有序时的排序十分高效。 对于随机排序的无重复主键的数组，插入排序和选择排序的运行时间是平方级别的，两者之比应该是一个较小的常数。具体测试时可以通过修改代码，统计不同算法解决同一问题所使用的比较总次数来进行算法性能比较。
冒泡排序*
public static void bubbleSort(Comparable[] a) {
int N = a.length;
for(int i =0; i<N-1; i++){
for(int j =0;j<N-1-i;j++){
if(less(a[j+1],a[j])){
exch(a,j,j+1);
}
}
}
}
希尔排序
希尔排序基于插入排序改进而来。对于大规模的乱序数组，插入排序很慢，因为它只会交换相邻的元素。希尔排序为了加快速度，使数组中任意间隔为h的元素都是有序的（h有序数组），即交换不相邻的元素以对数组的局部进行排序，并最终用插入排序（h最终为1）将局部有序数组排序。希尔排序需要选择一个递减序列，该序列最终收敛为1。（相当于在插入排序之外再加一层循环用来将h进行递减）
public static void shellSort(Comparable[] a) {
int N = a.length;
// 3x+1 increment sequence: 1, 4, 13, 40, 121, 364, 1093, ...
int h = 1;
while (h < N/3)
h = 3*h + 1;
while (h >= 1) {
// h-sort the array
for (int i = h; i < N; i++) {
for (int j = i; j >= h && less(a[j], a[j-h]); j -= h) {
exch(a, j, j-h);
}
}
h /= 3;
}
}
希尔排序时间复杂度与所选择的步长有关：
归并排序
归并算法基于归并操作，即将两个有序的数组归并成一个更大的有序数组。要将一个数组排序，可以先递归地将它分成两半分别排序，然后将结果归并起来。 归并排序能够保证将任意长度为N的数组排序所需时间和NlogN成正比。其主要缺点是所需的额外空间和N成正比。
// 原地归并方法：先将原数组整个拷贝，再合并回去
public static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
for (int k = lo; k <= hi; k++) {
aux[k] = a[k];
}
int i = lo, j = mid+1;
for (int k = lo; k <= hi; k++) {
if (i > mid) a[k] = aux[j++];
else if (j > hi) a[k] = aux[i++];
else if (less(aux[j], aux[i])) a[k] = aux[j++];
else a[k] = aux[i++];
}
}
// 实际的递归归并操作
private static void mergeSort(Comparable[] a, Comparable[] aux, int lo, int hi) {
if (hi <= lo)
return;
int mid = lo + (hi - lo) / 2;
mergeSort(a, aux, lo, mid);
mergeSort(a, aux, mid + 1, hi);
merge(a, aux, lo, mid, hi);
}
// 归并排序接口
public static void mergeSort(Comparable[] a) {
Comparable[] aux = new Comparable[a.length]; // 交换空间
mergeSort(a, aux, 0, a.length-1);
}
快速排序
快速排序将长度为N的数组排序所需的时间和NlogN成正比，且所需空间小于归并排序。 它将一个数组分成两个子数组，并将两部分独立地排序，该方法的关键在于切分：对于一个选定的元素，每次切分后使得该元素处于最终的位置，即其左边的元素都不大于它，而右边的元素都不小于它。
// 快速排序的切分操作
private static int partition(Comparable[] a, int lo, int hi) {
int i = lo;
int j = hi + 1;
Comparable v = a[lo]; // 选定第一个元素为切分基准
while (true) {
while (less(a[++i], v))
if (i == hi) break;
while (less(v, a[--j]))
if (j == lo) break;
if (i >= j)
break;
exch(a, i, j);
}
exch(a, lo, j);
return j;
}
// 快速排序的实际递归操作
private static void quickSort(Comparable[] a, int lo, int hi) {
if (hi <= lo)
return;
int j = partition(a, lo, hi);
quickSort(a, lo, j-1);
quickSort(a, j+1, hi);
}
// 快速排序的接口
public static void quickSort(Comparable[] a) {
quickSort(a, 0, a.length - 1);
}
堆排序
基于二叉堆的排序，二叉堆是一组能够用堆有序的完全二叉树排序的元素，并在数组中按层级存储。 完全二叉树：除最后一层外，每一层上的节点数均达到最大值；在最后一层上只缺少右边的若干结点。 叶子结点只可能在最大的两层上出现。对任意结点，若其右分支下的子孙最大层次为L，则其左分支下的子孙的最大层次必为L 或 L+1； 完全二叉树通常采用数组而不是链表存储，对于tree[i]，有如下特点： （1）若i为奇数且i>1，那么tree的左兄弟为tree[i-1]； （2）若i为偶数且i<n，那么tree的右兄弟为tree[i+1]； （3）若i>1，tree的双亲为tree[i div 2]； （4）若2i<=n，那么tree的左孩子为tree[2i]；若2i+1<=n，那么tree的右孩子为tree[2i+1]； （5）若i>n/2，那么tree[i]为叶子结点（对应于（3））； （6）若i<(n-1)/2，那么tree[i]必有两个孩子（对应于（4））。 （7）满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。 完全二叉树第i层至多有2^（i-1）个节点，共i层的完全二叉树最多有2^i-1个节点。
堆排序：使用堆下沉操作，将原始数组重新组织安排进一个大根堆中，然后将大根堆的顶部元素（当前大根堆中最大的元素）与数组空间的最后一个元素交换，这样最后一个元素就排好序了，然后用剩下的N-1个元素构造新的大根堆，继续以上操作。
// 大根堆下沉算法：k为待下沉元素索引，N为堆中最后一个元素的索引
private static void sink(Comparable[] a,int k,int N) {
while (2*k <= N) {
int j = 2*k;
if (j < N && less(a[j], a[j+1]))
j++;
if (!less(a[k], a[j]))
break;
exch(a,k,j);
k = j;
}
}
// 堆排序
public static void heapSort(Comparable[] a){
int N = a.length-1;
// 首先将指定数组调整为一个大根堆：从k=N/2的元素开始往前调整
for(int k= N/2; k>=0; k--){
sink(a,k,N);
}
// 去掉大根堆的堆顶元素，用剩下的元素重新构造堆。循环N次
while(N>0){
exch(a,0,N--);
sink(a,0,N);
}
}
计数排序*
一种稳定的线性时间排序算法。计数排序使用一个额外的数组，其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。 （略）
查找
无序链表中的顺序查找
public class SequentialSearchST<Key, Value> {
private Node first;
// 内部类，用来表示链表的节点
private class Node {
private Key key;
private Value val;
private Node next;
public Node(Key key, Value val, Node next) {
this.key = key;
this.val = val;
this.next = next;
}
}
// 根据键值进行查找
public Value get(Key key) {
for (Node x = first; x != null; x = x.next) {
if (key.equals(x.key)) return x.val;
}
return null;
}
// 往链表添加节点，相同键值的数据会被覆盖
public void put(Key key, Value val) {
for (Node x = first; x != null; x = x.next)
if (key.equals(x.key)) { x.val = val; return; }
first = new Node(key, val, first);
}
public static void main(String[] args) {
SequentialSearchST<String, String> st = new SequentialSearchST<String, String>();
st.put("www.cs.princeton.edu", "128.112.136.11");
st.put("www.princeton.edu", "128.112.130.211");
st.put("www.math.princeton.edu", "128.112.18.11");
...
System.out.println(st.get("www.cs.princeton.edu"));
}
}
有序数组中的二分查找
在N个键的有序数组中进行二分查找最多需要lgN+1次比较，无论成功与否。
public class BinarySearch<Key extends Comparable<Key>, Value> {
private Key[] keys;
private Value[] vals;
private int N = 0;
@SuppressWarnings("unchecked")
public BinarySearch(int capacity) {
keys = (Key[]) new Comparable[capacity];
vals = (Value[]) new Object[capacity];
}
// 在put时调用，当数组容量不够时扩容
@SuppressWarnings("unchecked")
private void resize(int capacity) {
Key[] tempk = (Key[]) new Comparable[capacity];
Value[] tempv = (Value[]) new Object[capacity];
for (int i = 0; i < N; i++) {
tempk[i] = keys[i];
tempv[i] = vals[i];
}
vals = tempv;
keys = tempk;
}
// 查询接口
public Value get(Key key) {
if (N==0)
return null;
int i = rank(key);
if (i < N && keys[i].compareTo(key) == 0) return vals[i];
return null;
}
// 返回表中小于给定键的键的数量 -- 循环版
public int rank(Key key) {
int lo = 0, hi = N-1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
int cmp = key.compareTo(keys[mid]);
if(cmp < 0) hi = mid - 1;
else if (cmp > 0) lo = mid + 1;
else return mid;
}
return lo;
}
// 返回表中小于给定键的键的数量 -- 递归版
public int rank(Key key,int lo,int hi) {
if( hi < lo )
return lo;
int mid = lo+(hi - lo)/2;
int cmp = key.compareTo(keys[mid]);
if( cmp<0 )
return rank(key,lo,mid-1);
else if(cmp>0)
return rank(key,mid+1,hi);
else
return mid;
}
// 在插入新元素前将所有较大的键向后移动一格
public void put(Key key, Value val) {
int i = rank(key);
if (i < N && keys[i].compareTo(key) == 0) {
vals[i] = val;
return;
}
if (N == keys.length) resize(2*keys.length);
for (int j = N; j > i; j--) {
keys[j] = keys[j-1];
vals[j] = vals[j-1];
}
keys[i] = key;
vals[i] = val;
N++;
}
public static void main(String[] args) {
BinarySearch<String, String> st = new BinarySearch<String, String>(10);
st.put("www.cs.princeton.edu", "128.112.136.11");
st.put("www.princeton.edu", "128.112.130.211");
...
st.put("www.iitb.ac.in", "202.68.145.210");
System.out.println(st.get("www.iitb.ac.in"));
}
}
二叉查找树
一棵二叉查找树是一棵二叉树，其中每个结点都含有一个Comparable的键及其相关联的值，且每个结点的键都大于其左子树中的任意结点的键而小于右子树的任意结点的值。
public class BST<Key extends Comparable<Key>, Value> {
private Node root;
private class Node {
private Key key;
private Value val;
private Node left, right;
private int N; // 含根节点在内的整个二叉树中的节点数
public Node(Key key, Value val, int N) {
this.key = key;
this.val = val;
this.N = N;
}
}
private int size(Node x) {
if (x == null) return 0;
else return x.N;
}
// 查找接口
public Value get(Key key) {
return get(root, key);
}
// 实际的递归查找
private Value get(Node x, Key key) {
if (x == null) return null;
int cmp = key.compareTo(x.key);
if (cmp < 0) return get(x.left, key);
else if (cmp > 0) return get(x.right, key);
else return x.val;
}
// 添加新节点的接口
public void put(Key key, Value val) {
root = put(root, key, val);
}
// 实际的递归添加
private Node put(Node x, Key key, Value val) {
if (x == null) return new Node(key, val, 1);
int cmp = key.compareTo(x.key);
if
(cmp < 0) x.left = put(x.left,key,val);
else
if (cmp > 0) x.right = put(x.right,key,val);
else
x.val = val;
x.N = 1 + size(x.left) + size(x.right);
return x;
}
public static void main(String[] args) {
BST<String, String> st = new BST<String, String>();
st.put("www.cs.princeton.edu", "128.112.136.11");
st.put("www.princeton.edu", "128.112.130.211");
st.put("www.math.princeton.edu", "128.112.18.11");
...
System.out.println(st.get("www.princeton.edu"));
}
}
红黑二叉查找树*
红黑树是一种平衡二叉树（AVL树）。平衡二叉树中任何节点的两个子树的高度最大差别为1，增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。
public class RedBlackBST<Key extends Comparable<Key>, Value> {
private static final boolean RED = true;
private static final boolean BLACK = false;
private Node root; // root of the BST
// BST helper node data type
private class Node {
private Key key; // key
private Value val; // associated data
private Node left, right; // links to left and right subtrees
private boolean color; // color of parent link
private int N; // subtree count
public Node(Key key, Value val, boolean color, int N) {
this.key = key;
this.val = val;
this.color = color;
this.N = N;
}
}
private boolean isRed(Node x) {
if (x == null) return false;
return (x.color == RED);
}
// number of node in subtree rooted at x; 0 if x is null
private int size(Node x) {
if (x == null) return 0;
return x.N;
}
// value associated with the given key; null if no such key
public Value get(Key key) { return get(root, key); }
// value associated with the given key in subtree rooted at x; null if no such key
private Value get(Node x, Key key) {
while (x != null) {
int cmp = key.compareTo(x.key);
if (cmp < 0) x = x.left;
else
if (cmp > 0) x = x.right;
else
return x.val;
}
return null;
}
public void put(Key key, Value val) {
root = put(root, key, val);
root.color = BLACK;
}
private Node put(Node h, Key key, Value val) {
if (h == null) return new Node(key, val, RED, 1);
int cmp = key.compareTo(h.key);
if (cmp < 0) h.left = put(h.left, key, val);
else if (cmp > 0) h.right = put(h.right, key, val);
else h.val = val;
// fix-up any right-leaning links
if (isRed(h.right) && !isRed(h.left)) h = rotateLeft(h);
if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h);
if (isRed(h.left) && isRed(h.right)) flipColors(h);
h.N = size(h.left) + size(h.right) + 1;
return h;
}
// make a left-leaning link lean to the right
private Node rotateRight(Node h) {
assert (h != null) && isRed(h.left);
Node x = h.left;
h.left = x.right;
x.right = h;
x.color = x.right.color;
x.right.color = RED;
x.N = h.N;
h.N = size(h.left) + size(h.right) + 1;
return x;
}
// make a right-leaning link lean to the left
private Node rotateLeft(Node h) {
assert (h != null) && isRed(h.right);
Node x = h.right;
h.right = x.left;
x.left = h;
x.color = x.left.color;
x.left.color = RED;
x.N = h.N;
h.N = size(h.left) + size(h.right) + 1;
return x;
}
// flip the colors of a node and its two children
private void flipColors(Node h) {
// h must have opposite color of its two children
assert (h != null) && (h.left != null) && (h.right != null);
assert (!isRed(h) && isRed(h.left) && isRed(h.right))
|| (isRed(h) && !isRed(h.left) && !isRed(h.right));
h.color = !h.color;
h.left.color = !h.left.color;
h.right.color = !h.right.color;
}
public static void main(String[] args) {
RedBlackBST<String, String> st = new RedBlackBST<String, String>();
st.put("www.cs.princeton.edu", "128.112.136.11");
st.put("www.princeton.edu", "128.112.130.211");
st.put("www.math.princeton.edu", "128.112.18.11");
...
System.out.println(st.get("www.princeton.edu"));
}
}
基于拉链法的散列表查找
所有hash值相同的节点（发生冲突了）都存放在同一个链表中。
public class SeparateChainingHashST<Key, Value> {
private int N;
private int M;
private SequentialSearchST<Key, Value>[] st; // 一个链表，用于存放hash结果相同的所有节点
public SeparateChainingHashST(int M) {
this.M = M;
st = (SequentialSearchST<Key, Value>[]) new SequentialSearchST[M];
for (int i = 0; i < M; i++)
st[i] = new SequentialSearchST<Key, Value>();
}
// 计算hash值
private int hash(Key key) {
return (key.hashCode() & 0x7fffffff) % M; // hashCode()是Object的方法
}
// 查找接口：先算出hash值用来确定所要查找的链表，再在该链表中用指定的key进行查找
public Value get(Key key) {
int i = hash(key);
return st[i].get(key);
}
// 往hash列表中加入节点
public void put(Key key, Value val) {
int i = hash(key);
if (!st[i].contains(key)) N++;
st[i].put(key, val);
}
}
基于线性探测法的散列表查找
用大小为M的数组保存N个键值对，M>N，依靠数组中的空位来解决碰撞冲突。算出hash值后，找到其在数组中对应的索引，检查改索引对应的值和被查找的值是否相同，如果不同则将索引增大继续查找，到达数组结尾时折回数组的开头，直到找到该键或者遇到一个空元素。
public class LinearProbingHashST<Key, Value> {
private int N;
private int M;
private Key[] keys;
private Value[] vals;
@SuppressWarnings("unchecked")
public LinearProbingHashST(int capacity) {
M = capacity;
keys = (Key[]) new Object[M];
vals = (Value[]) new Object[M];
}
private int hash(Key key) {
return (key.hashCode() & 0x7fffffff) % M;
}
private void resize(int capacity) {
LinearProbingHashST<Key, Value> temp = new LinearProbingHashST<Key, Value>(capacity);
for (int i = 0; i < M; i++) {
if (keys[i] != null) {
temp.put(keys[i], vals[i]);
}
}
keys = temp.keys;
vals = temp.vals;
M = temp.M;
}
// 往散列表表中插入数据
public void put(Key key, Value val) {
if (N >= M/2) resize(2*M);
int i;
for (i = hash(key); keys[i] != null; i = (i + 1) % M) {
if (keys[i].equals(key)) {
vals[i] = val;
return;
}
}
keys[i] = key;
vals[i] = val;
N++;
}
// 搜索
public Value get(Key key) {
for (int i = hash(key); keys[i] != null; i = (i + 1) % M)
if (keys[i].equals(key))
return vals[i];
return null;
}
public static void main(String[] args) {
LinearProbingHashST<String, String> st = new LinearProbingHashST<String, String>(10);
st.put("www.cs.princeton.edu", "128.112.136.11");
st.put("www.princeton.edu", "128.112.130.211");
...
System.out.println(st.get("www.cs.princeton.edu"));
}
}
图*
字符串
暴力子字符串查找算法一
public static int violenceSearch(String pat,String txt){
int M = pat.length();
int N = txt.length();
for(int i = 0; i <= N-M; i++){
int j;
for(j=0; j<M; j++)
if(txt.charAt(i+j) != pat.charAt(j))
break;
if(j == M)
return i;
}
return -1;
}
暴力子字符串查找算法二
显式回退：
public static int violenceSearch2(String pat,String txt){
int j,M = pat.length();
int i,N = txt.length();
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 -1;
}
KMP字符串查找算法
此算法通过运用对这个词在不匹配时本身就包含足够的信息来确定下一个匹配将在哪里开始的发现，从而避免重新检查先前匹配的字符。 具体而言就是针对搜索词，算出一张《部分匹配表》（Partial Match Table），当发生不匹配时，通过查表并结合如下公式来计算出需要后移的下一个匹配位置： 移动位数 = 已匹配的字符数 - 对应的部分匹配值
部分匹配表的生成算法： 首先，要了解两个概念：”前缀”和”后缀”。 “前缀”指除了最后一个字符以外，一个字符串的全部头部组合；”后缀”指除了第一个字符以外，一个字符串的全部尾部组合。 “部分匹配值”就是”前缀”和”后缀”的最长的共有元素的长度。以”ABCDABD”为例：
- “A”的前缀和后缀都为空集，共有元素的长度为0；
- “AB”的前缀为[A]，后缀为[B]，共有元素的长度为0；
- “ABC”的前缀为[A, AB]，后缀为[BC, C]，共有元素的长度0；
- “ABCD”的前缀为[A, AB, ABC]，后缀为[BCD, CD, D]，共有元素的长度为0；
- “ABCDA”的前缀为[A, AB, ABC, ABCD]，后缀为[BCDA, CDA, DA, A]，共有元素为”A”，长度为1；
- “ABCDAB”的前缀为[A, AB, ABC, ABCD, ABCDA]，后缀为[BCDAB, CDAB, DAB, AB, B]，共有元素为”AB”，长度为2；
- “ABCDABD”的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的长度为0。 最终的部分匹配表内容：
KMP匹配过程举例：
发生不匹配：
已知空格与D不匹配时，前面六个字符”ABCDAB”是匹配的。查表可知，最后一个匹配字符B对应的”部分匹配值”为2，因此移动的位数 = 已匹配的字符数6 - 部分匹配值2 ，为4，即将匹配开始位置后移4位后继续匹配：
因为空格与Ｃ不匹配，搜索词还要继续往后移。这时，已匹配的字符数为2（”AB”），对应的”部分匹配值”为0。所以，移动位数 = 2 - 0，结果为 2，于是将搜索词向后移2位继续匹配：
因为空格与A不匹配，继续后移一位：
逐位比较，直到发现C与D不匹配。于是，移动位数 = 6 - 2，继续将搜索词向后移动4位，继续匹配：
逐位比较，直到搜索词的最后一位，发现完全匹配，于是搜索完成。如果还要继续搜索（即找出全部匹配），移动位数 = 7 - 0，再将搜索词向后移动7位（7为已匹配的字符数，这里就是匹配字符串的总长度）。
public class KMP {
private final int R; // the radix
private int[][] dfa; // the KMP automoton
private String pat; // or the pattern string
// create the DFA from a String
public KMP(String pat) {
this.R = 256;
this.pat = pat;
// build DFA from pattern
int M = pat.length();
dfa = new int[R][M];
dfa[pat.charAt(0)][0] = 1;
for (int X = 0, j = 1; j < M; j++) {
for (int c = 0; c < R; c++)
dfa[c][j] = dfa[c][X]; // Copy mismatch cases.
dfa[pat.charAt(j)][j] = j+1; // Set match case.
X = dfa[pat.charAt(j)][X]; // Update restart state.
}
}
// return offset of first match; N if no match
public int search(String txt) {
// simulate operation of DFA on text
int M = pat.length();
int N = txt.length();
int i, j;
for (i = 0, j = 0; i < N && j < M; i++) {
j = dfa[txt.charAt(i)][j];
}
if (j == M) return i - M; // found
return N; // not found
}
public static void main(String[] args) {
String pat = "WINSTON";
String txt = "0123456789WINSTONdsiyghkadfadfafhdg";
KMP kmp = new KMP(pat);
int offset = kmp.search(txt);
System.out.println(offset);
}
}
BM字符串查找算法
BM算法的效率比KMP高，是一种从后往前扫描的算法。当某个字符不匹配时（坏字符），检查该主串中的不匹配的字符是否出现在匹配字符串中的其他位置，然后根据如下公式计算下一次匹配的位移数： 后移位数 = 坏字符的位置 - 搜索词中的上一次出现位置 如果”坏字符”不包含在搜索词之中，则上一次出现位置为 -1。 假定字符串为”HERE IS A SIMPLE EXAMPLE”，搜索词为”EXAMPLE”：
首先，”字符串”与”搜索词”头部对齐，从尾部开始比较。发现坏字符为‘S’，后移位数 = 坏字符S在搜索词中的当前匹配位置6（从0开始） - S在搜索词中的上一次出现的位置-1，为7.因此后移7位后继续匹配：
发现”P”与”E”不匹配，所以”P”是”坏字符”。但是，”P”包含在搜索词”EXAMPLE”之中。所以，后移位数 = 坏字符位置6 - 在搜索词中上一次出现的位置4，为2，因此后移2位再继续匹配：
“MPLE”与”MPLE”匹配。我们把这种情况称为”好后缀”（good suffix），即所有尾部匹配的字符串。注意，”MPLE”、”PLE”、”LE”、”E”都是好后缀。 发现”I”与”A”不匹配。所以，”I”是”坏字符”，但此时因为有好后缀的存在，所以不按之前的公式，而是按如下公式来计算位移： 后移位数 = 好后缀的位置 - 搜索词中的上一次出现位置
这个规则有三个注意点：
- “好后缀”的位置以最后一个字符为准。假定”ABCDEF”的”EF”是好后缀，则它的位置以”F”为准，即5（从0开始计算）。
- 如果”好后缀”在搜索词中只出现一次，则它的上一次出现位置为 -1。比如，”EF”在”ABCDEF”之中只出现一次，则它的上一次出现位置为-1（即未出现）。
- 如果”好后缀”有多个，则除了最长的那个”好后缀”，其他”好后缀”的上一次出现位置必须在头部。比如，假定”BABCDAB”的”好后缀”是”DAB”、”AB”、”B”，请问这时”好后缀”的上一次出现位置是什么？回答是，此时采用的好后缀是”B”，它的上一次出现位置是头部，即第0位。这个规则也可以这样表达：如果最长的那个”好后缀”只出现一次，则可以把搜索词改写成如下形式进行位置计算”(DA)BABCDAB”，即虚拟加入最前面的”DA”。
回到上文的这个例子。此时，所有的”好后缀”（MPLE、PLE、LE、E）之中，只有”E”在”EXAMPLE”还出现在头部，所以后移 6 - 0 = 6位。
可以看到，”坏字符规则”只能移3位，”好后缀规则”可以移6位。所以，Boyer-Moore算法的基本思想是，每次后移这两个规则之中的较大值。更巧妙的是，这两个规则的移动位数，只与搜索词有关，与原字符串无关。因此，可以预先计算生成《坏字符规则表》和《好后缀规则表》。使用时，只要查表比较一下就可以了。
继续从尾部开始比较，”P”与”E”不匹配，因此”P”是”坏字符”。根据”坏字符规则”，后移 6 - 4 = 2位。
从尾部开始逐位比较，发现全部匹配，于是搜索结束。如果还要继续查找（即找出全部匹配），则根据”好后缀规则”，后移 6 - 0 = 6位，即头部的”E”移到尾部的”E”的位置。
public class BoyerMoore {
private final int R; // the radix
private int[] right; // the bad-character skip array
private String pat; // or as a string
// pattern provided as a string
public BoyerMoore(String pat) {
this.R = 256;
this.pat = pat;
// position of rightmost occurrence of c in the pattern
right = new int[R];
for (int c = 0; c < R; c++)
right[c] = -1;
for (int j = 0; j < pat.length(); j++)
right[pat.charAt(j)] = j;
}
// return offset of first match; N if no match
public int search(String txt) {
int M = pat.length();
int N = txt.length();
int skip;
for (int i = 0; i <= N - M; i += skip) {
skip = 0;
for (int j = M-1; j >= 0; j--) {
if (pat.charAt(j) != txt.charAt(i+j)) {
skip = Math.max(1, j - right[txt.charAt(i+j)]);
break;
}
}
if (skip == 0) return i; // found
}
return N; // not found
}
public static void main(String[] args) {
String pat = "WINSTON";
String txt = "0123456789WINSTONdsiyghkadfadfafhdg";
BoyerMoore bm = new BoyerMoore(pat);
int offset = bm.search(txt);
System.out.println(offset);
}
}
RK字符串查找算法
Rabin-Karp算法的思想：
- 假设子串的长度为M，目标字符串的长度为N
- 计算子串的hash值
- 计算目标字符串中每个长度为M的子串的hash值（共需要计算N-M+1次）
- 比较hash值，如果hash值不同，字符串必然不匹配，如果hash值相同，还需要使用朴素算法再次判断 实现略。
补充*
求最大子序列和的联机算法
public class MaxSubsequenceSum {
public static int maxSubsequenceSum(int[] a){
int thisSum, maxSum, i;
int N = a.length;
thisSum = maxSum = 0;
// 只用一次循环
for( i=0; i<N; i++ ){
thisSum += a[i];
if( thisSum > maxSum )
maxSum = thisSum;
else if( thisSum < 0 ) // 当当前累加和为负数时，和置0
thisSum = 0;
}
return maxSum;
}
public static void main(String[] args) {
int[] a = {1,2,3,-4,4,-2,-9,9,9,9,-100,-7,9,9,9,-50,8,8,-8}; //
System.out.println(maxSubsequenceSum(a));
}
}
单链表相关操作
public class LinkList<Key, Value> {
private int N; // 链表长度
private Node first; // 头结点
// 链表结点
private class Node {
private Key key;
private Value val;
private Node next;
public Node(Key key, Value val, Node next) {
this.key = key;
this.val = val;
this.next = next;
}
}
// 搜索
public Value get(Key key) {
for (Node x = first; x != null; x = x.next) {
if (key.equals(x.key)){
return x.val;
}
}
return null;
}
// 添加新结点
public void put(Key key, Value val) {
for ( Node x = first; x != null; x = x.next ){
if ( key.equals(x.key) ) {
x.val = val;
return;
}
}
first = new Node(key, val, first);
}
// 删除结点
public void delete(Key key) {
first = delete(first, key);
}
// 递归删除结点
private Node delete(Node x, Key key) {
if (x == null)
return null;
if ( key.equals(x.key) ){
N--;
return x.next;
}
x.next = delete(x.next, key);
return x;
}
// 反转链表
public void reverse(){
Node prev = null;
Node curr = first;
while(curr!=null){
Node next = curr.next;
// next.next = curr;
curr.next = prev;
prev = curr;
curr = next;
}
first = prev;
}
// 打印链表
public void show(){
for (Node x = first; x != null; x = x.next){
System.out.print(x.key+"["+x.val+"] ");
}
System.out.println();
}
public static void main(String[] args) {
// 初始化、新增结点
LinkList<String, String> st = new LinkList<String, String>();
st.put("A","1");
st.put("B","2");
st.put("C","3");
st.put("D","4");
st.put("E","5");
st.put("F","6");
st.put("G","7");
st.put("H","8");
st.put("I","9");
st.put("J","10");
st.show();
// 查找
System.out.println(st.get("I"));
// 删除
String delKey = "I";
st.delete(delKey);
st.show();
// 反转
st.reverse();
st.show();
}
}
