一般的算法为什么这么低效呢?那是因为主串指针回溯情况过多:
主串指针如果不回溯的话,速度就会加快,那我们就会想:
如何让主串指针不回溯?
KMP算法就是解决了这个问题,所以速度变得更快速了。
它是这样子的:
用一个数组:next[] 求得失配时的位置,然后保存下来。
要说清楚KMP算法,可以从朴素的模式匹配算法说起。
朴素的模式匹配算法比较容易理解,其实现如下
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
26
27
28
29
|
int Index( char s[], char p[], int pos)
{
int i, j, slen, plen;
i = pos;
j = 0;
slen = strlen (s);
plen = strlen (p);
while ((i < slen) && (j < plen))
{
if ((s[i] == p[j]))
{
i++;
j++;
}
else
{
i = i-j+1;
j = 0;
}
}
if (j >= plen)
{
return (i-plen);
}
else
{
return -1;
}
}
|
可见,在朴素的模式匹配算法中,当模式中的p[j]与主串中的s[i]不匹配时,需要把主串的指针回溯到i-j+1的地方从新用s[i-j+1]跟p[0]进行匹配比较。KMP算法的想法是,能不能不回溯主串的指针呢?这种想法基于如下事实的:p[j]!=s[i]前,p[0]~p[j-1]跟s[i-j]~s[i-1]是匹配的(这里j>0,也就是说在不匹配前已经有匹配的字符了。否则如果j=0,则主串指针肯定不用回溯,直接向前变成i+1再跟p[0]比较就是了)
p[j]!=s[i]前,p[0]~p[j-1]跟s[i-j]~s[i-1]是匹配的,这说明了什么呢?这说明可以通过分析模式的p[0]~p[j-1]来分析s[i-j]~s[i-1]。如果模式中存在p[0]~p[k-1]=p[j-k]~p[j-1](共k个匹配的字符,且k是满足这个关系的最大值),则可以知道s[i-k]~s[j-1]跟[0]~p[k-1]是匹配的,那么,s[i]只需要跟p[k]进行比较就行了。而这个k是跟主串无关的,只需要分析模式串就可以求出来(这就是普通的教材中next[j]=k这个假设的由来,普通教材中总喜欢假设这个k值已经有了,如果你逻辑思维强还没有什么,不然或多或少会把你卡在这的)。亦即next[j]=k。
如果上述的p[0]~p[k-1]=p[j-k]~p[j-1]串不存在会怎么样呢?这说明p[j]前的串中不存在p[0]...=...p[j-1]的情况,就连p[0]也不等于p[j-1],也就是说p[0]~p[j-1]中所有以p[j-1]为结尾的子串跟模式p都是失配的。基于上面p[0]~p[j-1]=s[i-j]~s[i-1]的事实,可以断定s[i-j]~s[i-1]中所有以s[i-1]结尾的子串跟模式p都是失配,这说明把主串的指针回溯到i-j+1~i-1都是没有必要的,既然没有必要回溯,而s[i]!=p[j],则s[i只能跟p[0]进行比较匹配了。亦即next[j]=0。
特殊情况下,j=0,即s[i]!=p[0],这时不用再用s[i]来跟p中的其它字符比较了,变成用s[i+1]跟p[0]进行比较。为了统一,可以让next[0]=-1。在下一轮的比较中,判断到j=-1的情况时,让i=i+1,j=j+1,自然就形成s[i+1]跟p[0]比较的效果了。
KMP算法实现示例
具体请看如下程序:
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
|
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 101
void get_next( int *next, char *a, int la) /*求NEXT[]的值*/
{
int i=1,j=0 ;
next[1] = 0 ;
while ( i <= la) /*核心部分*/
{
if ( a[i] == a[j] || j == 0 )
{
j ++ ;
i ++ ;
if ( a[i] == a[j])
next[i] = next[j];
else
next[i] = j ;
}
else
j = next[j] ;
}
}
int str_kmp( int *next, char *A , char *a, int lA, int la) /* EASY*/
{
int i,j,k ;
i = 1 ;
j = 1 ;
while ( i<=lA && j <= la )
{
if (A[i] == a[j] || j == 0 )
{
i ++ ;
j ++ ;
}
else
j = next[j] ;
}
if ( j> la)
return i-j+1 ;
else
return -1 ;
}
int main( void )
{
int n,k;
int next[MAX]={0} ;
int lA=0,la =0 ;
char A[MAX],a[MAX] ;
scanf ( "%s %s" ,A,a) ;
lA = strlen (A);
la = strlen (a);
for (k=la-1; k>= 0 ;k --)
a[k+1] = a[k] ;
for (k=lA-1; k>= 0 ;k --)
A[k+1] = A[k] ;
get_next(next,a,la) ;
k = str_kmp(next,A,a,lA,la);
if ( -1 == k)
printf ( "Not Soulation!!! " );
else
printf ( "%d " ,k) ;
system ( "pause" );
return 0 ;
}
|