6.4 字符串模式匹配

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数组，使得当匹配之时遇到不匹配的字符，不用从头开始匹配，而是从模式字符串中重复且已经匹配过的部分开始。

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 指向模式串中重复部分的下一个字符
    } 

    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] 进行比较
   a. 相等，next[j] = k+1;
   b. 不等，令 k = next[k]
   I. k != 0，重复第三步
   II. k == 0, next[j] = 1