子字符串的一种基本操作就是子字符串查找：给定一段长度为N的文本和一个长度为M的模式字符串，在文本中找到一个和该模式相符的子字符串。
暴力子字符串查找算法
子字符串查找的一个最显而易见的方法就是在文本中模式可能匹配的任何地方检查匹配是否存在。我们实现的search()方法就是在文本字符串中查找模式字符串pat第一次出现的位置。我们使用了一个指针I来跟踪文本，一个指针j来跟踪模式。对于每一个i，代码先将j重置并将其不断增大，直到找到一个不匹配的字符或是模式结束为止。
public static int search(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==N) return i; //找到匹配
}
return N; //未找到匹配
}
在最坏的情况下，暴力子字符串查找算法在长度为N的文本中查找长度为M的模式需要~MN此字符串比较。
暴力子字符匹配算法的另一种实现被称为显示回退。程序使用了一个指针i跟踪文本和一个指针j跟踪模式。
public static int search(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 N;
}
Knuth-Morris-Pratt子字符串查找算法
KMP算法的基本思想是当出现不匹配时，就能知晓一部分文本的内容（因为在匹配失败之前它们已经和模式相匹配）。我们可以利用这些信息避免将指针回退到所有这些已知字符之前。
在KMP子字符查找算法中，不会回退文本指针I，而是使用一个数组dfa[][]来记录匹配的失败时模式指针j应该回退多远。对于每个字符c，在比较了c和pat.charAt(j)之后，dfa[c][j]表示的应该是和下个文本字符比较的模式字符的位置。在查找中，dfa[txt.charAt(i)][j]是在比较了txt.charAt(i)和pat.charAt(j)之后应该和txt.charAt(i+1)比较的模式字符位置。
只要计算出了dfa[][]数组，就得到了我们想要的子字符串查找算法：当i和j所指向的字符匹配失败时，模式可能匹配的下一位应该从i-dfa[txt.charAt(i)][j]处开始。说明这个过程的一种的方式是使用确定有限状态自动机。
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; //未找到匹配
}
自动机的行为是这样的：沿着装换dfa[txt.charAt(i)][j]前进并继续检查下一个字符（将i加1）。对于一个匹配的转换，就向右移动一位，因为dfa[pat.charAt(j)][j]的值总是j+1；对于一个非匹配的转换，就向左移动。自动机每次从左向右从文本中读取一个字符并移动到一个新的状态。我们还包含了一个不会进行任何转换的停止状态。自动机从状态0开始，如果自动机到达了状态M，那么就在文本中找到了模式匹配的一段子字符串。
那么现在问题的关键在于如何构造dfa。
//dfa数组的构造
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];
}
首先我们知道在dfa[][]数组中，所有dfa[pat.charAt(j)][j]都应该为j+1,因为这是匹配项，状态机应前进一位。
之后我们不妨来模拟匹配失败时发生的事情：匹配失败后，模式字符串应当向后移动直到可以重新匹配。注意到这一情形与我们使用dfa的时候是如此的相似——事实上就是一样的过程。在构造过程中，我们可以设置重启位置x，对于每个构造位置都刷新一次重启位置的值，并将dfa数组在x处的值赋给构造位置，以实现文本指针“回退”。观察后容易发现，重启位置实际上就是自身向后移动之后与移动之前比较可以完全匹配的第一个位置，因此x的新值就等于dfa[pat.charAt(j)][x]。
以下为完整的kmp算法代码
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;
}
public static void main(String[] args){
String pat = args[0];
String txt = args[1];
KMP kmp = new KMP(pat);
StdOut.println("text: " + txt);
int offset = kmp.search(txt);
StdOut.print("pattern: ");
for(int i=0; i<offset; i++)
StdOut.print(" ");
StdOut.println(pat);
}
}
对于长度为M的模式字符串和长度为N的文本，KMP算法访问的字符不会超过M+N个。
