串
串的模式匹配算法
- 目的：确定主串中所含子串第一次出现的位置（定位）
- 算法：BF算法（又称古典的、经典的、朴素的、穷举的）；KMP算法（特点：速度快）
BF（Brute Force）算法思想：
将主串的第i个字符和模式（目标串）的第一个字符比较，若相等，继续逐个比较后续字符；若不等，从主串的下一字符起，重新与模式的第一个字符比较；直到主串的一个连续子串字符序列与模式相等。返回值为S中与T匹配的子序列第一个字符的序号，即匹配成功。否则，匹配失败，返回值 0。
//思路一
public static int bfMatch(String s,String t){
int index = 0, j = 0;
for (int i = 0; i < s.length();) {
if (s.charAt(i) == t.charAt(j)) {
if (j == t.length() - 1)
return index;
i++;
j++;
} else {
index++;
i = index;
j = 0;
}
if (i >= s.length())
break;
}
return -1;
}
//思路二
public static int bfMatch(String s,String t){
int j = 0,i = 0;
while(i < s.length() && j < t.length()){
if(s.charAt(i) == t.charAt(j)){
i++;
j++;
} else {
i = i - j + 1;
j = 0;
}
}
if(j == t.length())
return i - j;
else
return -1;
}时间复杂度分析：
若n为主串长度，m为子串长度，最坏情况是 主串前面n-m个位置都部分匹配到子串的最后一位，即这n-m位各比较了m次，最后m位也各比较了1次。即总次数为：
(n-m)*m+m = (n-m+1)*m若m << n，则算法复杂度O(n*m).
KMP（Knuth Morris Pratt）算法:
思想：
与朴素算法不同，朴素算法是当遇到不匹配字符时，向后移动一位继续匹配，而KMP算法是当遇到不匹配字符时，不是简单的向后移一位字符，而是根据前面已匹配的字符数和模式串前缀和后缀的最大相同字符串长度数组next的元素来确定向后移动的位数，所以KMP算法的时间复杂度比朴素算法的要少，并且是线性时间复杂度，即预处理时间复杂度是O(m)，匹配时间复杂度是O(n)。
核心：
kmp算法的核心即是计算模式串每一个位置之前的字符串的前缀和后缀公共部分的最大长度（不包括字符串本身，否则最大长度始终是字符串本身）。获得f每一个位置的最大公共长度之后，就可以利用该最大公共长度快速和字符串O比较。当每次比较到两个字符串的字符不同时，我们就可以根据最大公共长度将字符串f向前移动(已匹配长度-最大公共长度)位，接着继续比较下一个位置。事实上，字符串f的前移只是概念上的前移，只要我们在比较的时候从最大公共长度之后比较f和O即可达到字符串f前移的目的。
部分匹配表：
“前缀”指除了最后一个字符以外，一个字符串的全部头部组合；”后缀”指除了第一个字符以外，一个字符串的全部尾部组合。 
“部分匹配值”就是”前缀”和”后缀”的最长的共有元素的长度。以”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。
”部分匹配”的实质是，有时候，字符串头部和尾部会有重复。比如，”ABCDAB”之中有两个”AB”，那么它的”部分匹配值”就是2（”AB”的长度）。搜索词移动的时候，第一个”AB”向后移动 4 位（字符串长度-部分匹配值），就可以来到第二个”AB”的位置。
next数组求解及代码实现：
即求得模式串中每一个位置的最大公共长度。这个最大公共长度在算法导论里面被记为next数组，即上述部分匹配表整体右移一位，然后初始值赋为-1。见下图：
public static int []getKMPNext(String t){
int [] next = new int [t.length()];
next[0] = -1;//初始化
int j = 0,k = -1;
while(j < t.length() - 1){
if(k == -1 || t.charAt(j) == t.charAt(k)){
++k;
++j;
if(t.charAt(j) != t.charAt(k))
next[j] = k;//如果只有这一行，还不是最优
else
//因为不能出现p[j] = p[next[j]]，所以当出现时需要继续递归，
//k = next[k] = next[next[k]]
next[j] = next[k];
} else {
k = next[k];
}
}
return next;
}利用next数组进行KMP匹配
public static int kmpMatch(String s,String t,int []next){
int i = 0,j = 0;
while(i < s.length() && j < t.length()){
//如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++
if(j == -1 || s.charAt(i) == t.charAt(j)){
i++;
j++;
} else {
//如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令i不变，j = next[j]
//next[j]即为j所对应的next值
j = next[j];
}
}
if(j == t.length())
return i - j;
else
return -1;
}得到next值后，失配时，模式串向右移动的位数为：失配字符所在位置 - 失配字符对应的next值
额外补充
标准库为啥要采用BF而不采用KMP，BM?
The more advanced string search algorithms have a non-trivial setup time. If you are doing a once-off string search involving a not-too-large target string, you will find that you spend more time on the setup than you save during the string search.And even just testing the lengths of the target and search string is not going to give a good answer as to whether it is “worth it” to use an advanced algorithm. The actual speedup you get from (say) Boyer-Moore depends on the values of the strings; i.e. the character patterns.
The Java implementors have take the pragmatic approach. They cannot guarantee that an advanced algorithm will give better performance, either on average, or for specific inputs. Therefore they have left it to the programmer to deal with … where necessary.
大概意思就是，像KMP，BM这些高级算法的会有预处理时间和会消耗一些空间，在处理一些不是非常大的字符串的时候，时间不会有太大优势，而且还会占用一些空间。