1. 樸素模式匹配算法（又叫 簡單模式匹配算法）

• 基本思路：暴力匹配，從第一個字符開始，挨個匹配，如果不符合，則從第二個字符開始，挨個匹配。

int Index(string s, string t)
{
    int i = 0, j = 0;
    while(i <= length(s) && j <=length(t))
    {
        if(s[i] == t[j])
        {
            i++;
            j++;
        }else
        {
            i = i - j + 2; //指向s字符串中下一個字符
            j = 0;
        }
     }

     //如果此時 j 大于length(t)，則匹配成功，返回 i  - length(t)即匹配字符串起始位置
     if(j > length(t))  return i - length(t);
     else  return 0;
}

2. 首尾匹配算法

基本思路：從第一個字符開始，首先匹配字符串的首尾是否相符，如果相符再挨個匹配。不然，從下一個字符開始匹配。

while( i <= length(s) && j <= length(t))
{
    if ( s[i] == t[j] && s[i - 1 + length(t)] == t[j - 1 + length(t)] ) //首尾匹配
    {
        i++;
        k = i;
        j++;
        while(s[i] == t[j]) //匹配首尾之間的的字符
        {
            i++;
            j++;
        }

        if (j == length(t))
            return  i - length(t);
                 
    }else{
        i++;
        j = 0;
    }
}
return -1;

3. KMP模式匹配算法

基本思路：通過計算next數(shù)組，使得當(dāng)匹配之時遇到不匹配的字符，不用從頭開始匹配，而是從模式字符串中重復(fù)且已經(jīng)匹配過的部分開始。

int KMP(string s, string t, int next[])
{
    int i = 0 , j = 0;

    while(i <= length(s) && j <= length(t))
    {
        if (j == 0 || s[i] == t[j])
        {
            i++;
            j++;
        }else
            j = next[j];  //如果不匹配， j 指向模式串中重復(fù)部分的下一個字符
    } 

    if (j > t[0])
        return i - t[0];
    else
        return -1;
}

• 計算next的方法：

1. next[1] = 0 , next[2] = 1
2. 后面解每一位的next[j]值時，令 k = next[j - 1]
3. 將 s[j - 1]與s[k] 進(jìn)行比較
   a. 相等，next[j] = k+1;
   b. 不等，令 k = next[k]
   I. k != 0，重復(fù)第三步
   II. k == 0, next[j] = 1