在一个字符串（目标串）中查找一个子串（模式串）是否存在，如若查找成功返回子串第一个字符位置，否则查找失败。

暴力匹配

主串的第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数组的思想还可以解决很多字符串中的问题。