在一个字符串（目标串）中查找一个子串（模式串）是否存在，如若查找成功返回子串第一个字符位置，否则查找失败。
暴力匹配
主串的第i个字符如果与子串第一个字符匹配，则依次比较后边的字符，如果未完全匹配成功，也就是说后边有一个字符不一致，下一轮的匹配从主串的第i+1个与子串的第一个重新进行，直到匹配成功，返回下标，否则匹配失败。
该算法效率很低，每次匹配失败都要重新匹配，最坏情况下O(n*m)的复杂度，很多时候不能满足我们的要求。
int blfind(String S,String T){
int i=0,j=0;
while(i<S.length() && j<T.length()){
if(S[i]==T[j]){
i++;
j++;
}
else{
i=i-j+1;
j=0;
}
}
if(j==T.length() return i-j;
else return -1;
}
KMP模式匹配算法
先前我们是在不匹配的时候返回主串的头部继续匹配，我们可以想办法优化这种做法，当主串 S[i]与T[j]失配，我们不再移动i指针，而是移动j指针。大家想一下s[i]之前匹配成功的部分，是不是和T[0]-T[j-1]是一样的，如果找出T[0]到T[j-1]的相同前后缀的长度，是不是可以直接将j移动到相同前缀的下一个位置。
ababcababa 主串
ababa子串
我们在匹配到'a'和'c' 不等的时候 子串中abab 前缀ab 和后缀ab是相同的，它的前缀和主串中已经匹配的后缀一定是相同的 ，所以j指向子串中ababa的第三个字符‘a’，而i仍然指向c ，再次进行匹配，如若失配，不断地调整j指针就可以。
如何解决最长公共前后缀的问题，我们采用的next数组。
void getNext(){ //求next数组,这里T是模式串
next[0]=-1; //因为我们是求0到j-1的，所以0初始化为-1.
int j=0,k=-1;
while(j<T.length()-1){
if(k==-1 || T[j]==T[k])
next[++j]=++k; //next[j]表示 当S[i]和T[j]失配时，j指针的位置
else
k=next[k]; //这里非常巧妙，回溯的思想。 next[k]是T[k]之前字符串的最长公共前后缀，
// 而T[next[k]]就是这个最长公共前后缀中前缀的最后一个字符
}
}
int KMP() {
int i = 0;
int j = 0;
getNext();
while (i < S.length() && j < T.length()) {
if (S[i] == T[j]) {
i++;
j++;
}
else if(next[j]==-1) i++;
else j = next[j];
}
if (j == T.length())
return i - j;
else
return -1;
}
它的时间复杂度是O(n+m)，很高效，此外，next数组的思想还可以解决很多字符串中的问题。
