<字符串匹配>KMP算法为何比暴力求解的时间复杂度更低?

str表示文本串,m表示模式串;

str[i] 和 m[j] 是正在进行匹配比较的字符;

KMP的时间复杂度是O(m+n) , 暴力求解的时间复杂度是O(m*n)

KMP利用了m[ 0 : j-1 ]和str[ i-j : i-1 ]是相同的这一点,而暴力求解显然做不到.

int kmp(string str,string m)

{

    int next[MAXN];

    next[] = -;

    int i=;

    int j=-;

    while(i<m.size())

    {

        if(j==- || m[i]==m[j])

        {

            i++;

            j++;

            next[i] = j;

        }

        else

        {

            j = next[j];

        }

    }

    i=;

    j=;

    while(i<str.size() && j<m.size())

    {

        if(j==- || str[i]==m[j])

        {

            i++;

            j++;

        }

        else

        {

            j =next[j];

        }
　　　　 if(j==m.size()-1)
　　　　 {
　　　　　　return i-j;
　　　　 }

    }
　　 return -1;

}

巴特西

<字符串匹配>KMP算法为何比暴力求解的时间复杂度更低?

最新文章

热门文章