1、串的定义
这里所说的串指的是字串，就是字符串，当然不是烧烤串。计算机的字串是用编码形式保存的，通常的ASCII码，Unicode编码，中文的GBK等等。对于一个字串，定义为s="a1a2a3....an"，相应的对于另一个字串t=b1b2b2b3....bm，当且仅当n=m，且a1=b1,a2=b2,a3=b3....,an=bm，则两串相等。同时，当满足如下条件时s<t：
- n< m ， 且a1=b1(i=1,2,3....n)；
- 有k<=min(m,n)，使ai=bi(i=1,2,3,4,5...k-1)，ak<bk;(这种情况会根据编码计算，可能不同语言有不同处理)
2、朴素的模式匹配算法
模式匹配最先能想到的就是在一片文章中找到指定的单词，如文本的检索，引申到单词的统计。我们最简单想到的就是将材料文本当做一个很长的串，然后用对应的单词去匹配，具体是按照单词的字符一个个匹配，如果匹配到，继续，直到单词尾部，这是最理想的情况，否则，单词首字符再去比较文本第二个字符，依次直到获得结果。归纳如下：
- 匹配到，检索词，文本串同时推进；
- 未匹配到，检索词再去执行1，从文本串上次匹配的下一个字符开始；
朴素模式匹配算法的时间复杂度为最好为，最差是
代码如下
c++
//不存在匹配，返回0，长度存在t[0],s[0]
//s 待匹配，t匹配字串
//t 不空
int index(String s, String t, int pos){
int i = pos;
int j = 1;
while( i <= s[0] && j <= t[0]){
if(s[i] == t[j]){
++i;
++j;
}else{
i = i - j + 2; //从下一个位置开始
j = 1; //回到首位比较
}
}
if( j > t[0]){
return i - t[0];
}else{
return 0;
}
}
java
public class StringPattern {
public static void main(String[] args) {
String s = "dsfandkfnadsognoadsngasfsdbvonasdobvnadsodfnasonfo3n2n";
String p = "";
System.out.println(index(s, p));
}
private static int index(String s, String p) {
if (s == null || p == null || "".equals(p)) {
return -1;
}
int i = 0, j = 0;
while (i < s.length() && j < p.length()) {
if (s.charAt(i) == p.charAt(j)) {
i++;
j++;
} else {
i = i - j + 1;
j = 0;
}
}
if (j >= p.length()) {
return i - j;
}
return -1;
}
}
3、KMP模式匹配
KMP算法是D.E.Knuth、J.H.Morris以及V.R.Pratt的发明，可以避免重复遍历的算法，大大提高匹配效率。KMP有些难以理解，这种算法是典型的通过对客观规律的总结，来归纳出一个合理的算法，再通过编程实现和优化的结果。我们看到的只有分析过程和算法结果，并对这个结果加以运用。我尽量简洁的来表述这个算法，会对一些难点进行重点强调和解释。本文是KMP的初级介绍，后面会专门介绍KMP的优化方案。
3.1 KMP原理
首先看下朴素匹配可以优化的点。例如：在S=abcdefgab中匹配T=abcdex，朴素算法首先从a一直匹配到f-x,第6位。然后下次匹配再从T-a去匹配S-b，一直到T-a匹配S-c，一直到再匹配到S-f,T-a。重点：这里我们能够发现，字串T中，首字母a与他之后的字符都不相等，因此之后关于T-a和S中随后字符的比较没有必要进行，这是因为在第一次比较就知道S中往后的都是不等的。推理如下：
图示
由于我们得到这种经验，如果匹配的串T和目标串S有连续相同的元素，则跳过比较，且这种情况会导致T中j值的变化。所以对于另一种情况如
S=abcabaabca,T=abcabx，由于T=(ab)c(ab)x，这里第一次j=1，后面j直接为3，即比较到c的位置，j的取值表示了当期字符之前的串在串中的相似度，相似度越高，j越大。我们将T各个位置上j值的变化表示为一个next的数组保存，抽象成函数表示为：3.2 next数组推理和使用
- T=abcdex
j=1，next[1]=0；j=2，子串为a，其他情况next[2]=1；当j=3，子串ab，a!=b，按公式为其他情况，next[3]=1，最终的结果next[j]=011111 - T=abcabx
j=1，next[1]=0；j=2，next[2]=1，其他情况；j=3，子串ab，a!=b，其他情况,next[3]=1；j=4，子串bc，b!=c，其他情况,next[4]=1；j=5，子串abca，a和租后一个a相同，且有p1pk-1=p5-k+1p5-1，有p1=p4，因此k=2，next[5]=3;当j=6，子串(ab)c(ab)，有首ab=尾ab，p1p2=p4p5即p1pk-1=p6-k+1p5，得到next[6]=3
因此得到，注意一个例子中k值取最终最大的值。
KMP的时间复杂度为
3.3 算法实现
c++
//获取匹配串next数组
void get_next(String t, int *index){
int i,j;
i=1;
j=0;
next[1]=0;
while( i < t[0]) {
if( j==0 || t[i] == t[j]){
++i;
++j;
next[i] = j;
}else{
j = next[j];//没有相同，j保持前值
}
}
}
int index_kmp(String s ,String t, int pos){
int i = pos;
int j = 1;
int next[255];
get_index(t,next);
while(i<s[0] && j<= t[0]){
if(j == 0 || s[i] == t[j]){
++i;
++j;
}else{
j = next[j]
}
}
if( j > t [0]){
return i - t[0];
return 0;
}
可以看到和朴素算法差别不大，主要在于next数组的区别
java
public class StringPattern {
public static void main(String[] args) {
String s = "abcdexfgab";
String p = "exf";
System.out.println(index(s, p));
System.out.println(indexKmp(s,p));
}
private static int index(String s, String p) {
if (s == null || p == null || "".equals(p)) {
return -1;
}
int i = 0, j = 0;
while (i < s.length() && j < p.length()) {
if (s.charAt(i) == p.charAt(j)) {
i++;
j++;
} else {
i = i - j + 1;
j = 0;
}
}
if (j >= p.length()) {
return i - j;
}
return -1;
}
private static int indexKmp(String s, String p) {
if (s == null || p == null || "".equals(p)) {
return -1;
}
int i = 0, j = 0;
int[] next = nextArray(p);
while (i < s.length() && j < p.length()) {
if (j == -1 || s.charAt(i) == p.charAt(j)) {
i++;
j++;
} else {
j = next[j];
}
}
if (j >= p.length()) {
return i - j;
}
return -1;
}
private static int[] nextArray(String p) {
int[] next = new int[p.length()];
int j = 1;
int k = -1;
next[0] = -1;
while (j < p.length() - 1) {
if (k == -1 || p.charAt(j) == p.charAt(k)) {
++j;
++k;
next[j] = k;
}else {
k = next[k];
}
}
return next;
}
}
