字符串

KMP

Posted by Liao on 2020-02-19

1.求前缀表next[]

为什么要求前缀表？

如果用暴力的双指针，在失配的时候又从模式串的开头重新匹配，增加了回溯的次数，效率低，复杂度为O(m*n)。

前面已经匹配上的不用再搜索，通过next[]数组，在失去匹配的地方找到该元素的前后缀个数n，移动到模式串的下标n。复杂度时O(m+n)。

通俗来说，next数组存放每个元素之前的字符串，最长公共前后缀的个数。

如何求next[]呢？

Text: A B A B A B A B C A B A A B

Pattern: A B A B C A B A A

最长公共前缀个数 前缀
-1
0 A
0 AB
1 ABA
2 ABAB
0 ABABC
1 ABABCA
2 ABABCAB
3 ABABCABA

注意 最长前缀最后一个字符是不要的，故把next[0]初始化为-1，对应到模式串的每一个字符。

Pattern: A B A B C A B A A

next[]={-1,0, 0, 1, 2, 0, 1, 2, 3}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void getNext(int next[],string pattern,int n)
{
    next[0] = -1;
    int k = -1;  
    for(int i=1;i<n;i++)
    {
        while(k>-1 && pattern[i] != pattern[k+1])
            k = next[k];
        if(pattern[i] == pattern[k+1])
            k += 1;
        next[i] = k;
    }
    for(int i=n-1;i>0;i--)
        next[i] = next[i-1]+1;
}

2.KMP的实现过程

主串和匹配串依次匹配，当在失配的地方，查看当前next[i]，模式串从Pattern[next[i]]开始进行匹配

3

haystack：主串

needle：模式串

return：如果能找到，返回主串出现模式串的第一个下标；否则返回-1；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

int kmp(string haystack, string needle) {
    int len1 = haystack.size();
    int len2 = needle.size();
    if(len2 == 0)
        return 0;
    int next[100000];
    getNext(next,needle,len2);
    int i=0,j=0;
    while(i<len1 && j<len2)
    {
        if(j == -1 || haystack[i] == needle[j])
        {
            i++;
            j++;
        }
        else
        {
            j = next[j];
        }
        if(j >= len2)
            return i-len2;
    }
    return -1;
}
FEATURED TAGS
字符串
FRIENDS