字符串算法

1) 查询字符串S是否包含子串S1。主要思想是：如果S包含S1，那么S1必定是S的某个后缀的前缀；又因为S的后缀树包含了所有的后缀，所以只需对S的后缀树使用和Trie相同的查找方法查找S1即可（使用后缀树实现的复杂度同流行的KMP算法的复杂度相当）。

2) 找出字符串S的最长重复子串S1。比如abcdabcefda里abc同da都重复出现，而最长重复子串是abc。

3) 找出字符串S1同S2的最长公共子串。注意最长公共子串（Longest CommonSubstring）和最长公共子序列（LongestCommon Subsequence, LCS）的区别：子串（Substring）是串的一个连续的部分，子序列（Subsequence）则是从不改变序列的顺序，而从序列中去掉任意的元素而获得的新序列；更简略地说，前者（子串）的字符的位置必须连续，后者（子序列LCS）则不必。比如字符串acdfg同akdfc的最长公共子串为df，而他们的最长公共子序列是adf。LCS可以使用动态规划法解决。

4) Ziv-Lampel无损压缩算法。 LZW算法的基本原理是利用编码数据本身存在字符串重复特性来实现数据压缩，所以一个很好的选择是使用后缀树的形式来组织存储字符串及其对应压缩码值的字典。

5) 找出字符串S的最长回文子串S1。例如：XMADAMYX的最长回文子串是MADAM（此即为上面所说的第二个问题：最长回文问题，本文第二部分将详细阐述此问题）。

6) 多模式串的模式匹配问题（suffix_array + 二分）。

http://blog.csdn.net/v_july_v/article/details/6897097

KMP　算法

KMP算法的核心就是避免不必要的回溯，利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的．在KMP算法中不会回退主串的指针i，而是使用数组dfa[][]来记录匹配失败时模式串指针j应该回退到什么位置．

public class KMP {
	private String pat;
	private int[][] dfa;
	public KMP(String pat){
		this.pat = pat;
		int M = pat.length();
		int R = 256;
		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]; //复制匹配失败情况下的值
			dfa[pat.charAt(j)][j] = j+1;//设置匹配成功情况下的值
			X = dfa[pat.charAt(j)][X]; //更新重启状态
		}
	}
	public int search(String txt){
		int i,j,N = txt.length(),M= pat.length();
		for(i = 0, j = 0; i < N && j < M ; i++)
			j = dfa[txt.charAt(i)][j];
		if(j == M) return i - M;
		else return N;
	}
}

找出字符串S的最长回文子串S1

Manacher算法，其时间复杂度为O(n)
首先用一个非常巧妙的方式,在每个字符的两边都插入一个特殊的符号，使得所有可能的奇数/偶数长度的回文子串都转换成了奇数长度．

原串： waabwswfd
新串： #w#a#a#b#w#s#w#f#d#
辅助数组P： 1 2 1 2 3 2 1 2 1 2 1 4 1 2 1 2 1 2 1
这里有一个很好的性质，P［id］-1就是该回文子串在原串中的长度（包括‘#’）。
用rad[id]表示第i个字符的回文半径，rad[id]的最小值为1．　假设现在求出了rad[1, …, id]，现在要求后面的rad值，再假设现在有个指针k，从1循环到rad[i]，试图通过某些手段来求出[id + 1, id + rad[id] - 1]的rad值.

public static String getPalindromeLength(String str) {
    // 1.构造新的字符串
    // 为了避免奇数回文和偶数回文的不同处理问题，在原字符串中插入'#'，将所有回文变成奇数回文
    StringBuilder newStr = new StringBuilder();
    newStr.append('#');
    for (int i = 0; i < str.length(); i ++) {
        newStr.append(str.charAt(i));
        newStr.append('#');
    }
    // rad[i]表示以i为中心的回文的最大半径，i至少为1，即该字符本身
    int [] rad = new int[newStr.length()];
    // right表示已知的回文中，最右的边界的坐标
    int right = -1;
    // id表示已知的回文中，拥有最右边界的回文的中点坐标
    int id = -1;
    // 2.计算所有的rad
    // 这个算法是O(n)的，因为right只会随着里层while的迭代而增长，不会减少。
    for (int i = 0; i < newStr.length(); i ++) {
        // 2.1.确定一个最小的半径
        int r = 1;
        if (i <= right){
        	// rad[id] - i + id = mx - i
        	// j = 2 * id - i 
            r = Math.min(rad[id] + id - i , rad[2 * id - i]);
        }
        // 2.2.尝试更大的半径
        while (i - r >= 0 && i + r < newStr.length() 
        		&& newStr.charAt(i - r) == newStr.charAt(i + r)) {
            r++;
        }
        // 2.3.更新边界和回文中心坐标
        if (i + r - 1 > right) {
            right = i + r - 1;
            id = i;
        }
        rad[i] = r;
    }
    // 3.扫描一遍rad数组，找出最大的半径
    int maxLength = 0;
    int idx = 0;
    for (int i = 0; i < rad.length ; i++) {
        if (rad[i] > maxLength) {
            maxLength = rad[i];
            idx = i;
        }
    }
    StringBuilder sb = new StringBuilder();
    for(int i = idx - maxLength; i <= idx + maxLength; i++){
    	if(newStr.charAt(i) != '#')
    		sb.append(newStr.charAt(i));
    }
    return sb.toString();
}

http://blog.sina.com.cn/s/blog_3fe961ae0101iwc2.html
http://www.cnblogs.com/biyeymyhjob/archive/2012/10/04/2711527.html

KMP 算法

找出字符串S的最长回文子串S1

KMP　算法