BF和KMP算法 | 人雁南飞 转身一瞥你噙泪
Cobb 626 1

思路

BF和KMP算法 | 人雁南飞 转身一瞥你噙泪


/*
    前缀               后缀       j
p0...pk-1   ==    pj-k...pj-1    x
                                 next[j] = k  

思路中为啥回退 k = next[k] 个?
问题转化:前面看成子串,后面看成母串,在母串中搜索子串的问题。
找公共前后缀最大长度就行。 

优化:
ABCABED
ABCABC
-1 0 0 0 1 2       
回退的时候,回退的字符和要回退的字符相同,继续回退,子串中的 C 和 C,
所以C的next数组中的值因该是 0, 连续回退了
-1 0 0 0 1 0
*/
int* GetNext(char* sub)
{
    // next数组长度和子串长度相同
    int* next = new int[strlen(sub)];
    // 如果第一个元素就不匹配,主串前进一步。
    int k = -1; // next数组对应位置的值
    int j = 0;  // 下标
    next[j] = k;

    // j 下标  k 值
    while ( j < strlen(sub) - 1)  // 每一个字符记录的是之前的公共前后缀的长度,最后一个不用计算
    {
        // ABCABC  都在 B B位置,  都要前进1个,此时公共前后缀长度记录在C对应的数组中
        if ( k == -1 || sub[k] == sub[j])  
        {
            k++;
            j++;

            // 如果子串自己的字符和回退的字符相等  ABCABC
            if ( sub[k] == sub[j]) 
            {
                 // 就连续回退
                next[j] = next[k]; 
            }
            else
            {
                // 记录公共前后缀长度
                next[j] = k;   
            }
        }
        else
        {
            // pk != pj   
            // pk和pj比较失败 k值回退到比较失败的字符之前的公共前后缀的长度
            k = next[k];
        }
    }
    return next;
}

// i和j 两个字符串
// KMP把朴素算法中没有必要的步骤,优化掉了, 不符合匹配的时候,i不变,j回退。
// next[]数组中第一个值,-1 表示首字母都不同, i往后+1.
int KMP(char* main, char* sub)
{
    int size1 = strlen(main);
    int size2 = strlen(sub);

    int i = 0, j = 0;
    int* next = GetNext(sub);
    while (i < size1 && j < size2)
    {
        if (j == -1 || main[i] == sub[j])
        {
            i++;
            j++;
        }
        else
        {
                        //i = i - j + 1;    // BF中
                        //j = 0; 
            j = next[j];   // 匹配失败后,j下一次要回退的值
        }
    }

    if (j == size2)  // 如果j是自己的长度
    {
        return i - j; // 返回匹配的字符串在主串中的下标
    }
    else
    {
        return -1;
    }
}


int main()
{
    char mainStr[] = "abcabdef";
    char subStr[] = "abd";
    int pos = KMP(mainStr, subStr);
    cout << pos << endl;
}

评论区