KMP 算法
KMP 算法是一种改进的字符串匹配算法，KMP 算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next()函数，函数本身包含了模式串的局部匹配信息。时间复杂度
O
(
m
+
n
)
O(m+n)
O(m+n)。
朴素做法
你有两个串 ababbaba、aba，求第二个串在第一个串中出现了多少次。
设两串的长度分别为
n
,
m
n,m
n,m，则时间复杂度
O
(
n
m
)
O(nm)
O(nm)。
我们看到，标 ☆ 的几步可以优化。那应该怎么优化呢？
next 数组
我们发现，当一个串匹配失败时，不总是需要再次从头开始匹配。如果这个串有公共的前后缀，那么可以节约时间。
那我们就在这方面下点功夫。设
n
e
x
t
[
x
]
next[x]
next[x] 表示这个串前
x
x
x 位的公共的前后缀的最大长度，且
n
e
x
t
[
x
]
<
x
next[x]<x
next[x]<x，
x
∈
[
1
,
l
e
n
]
x\in[1,len]
x∈[1,len]，
l
e
n
len
len 表示这个串的长度。
以下为求
n
e
x
t
next
next 数组的步骤。 定义两个指针
i
=
2
,
j
=
0
i=2,j=0
i=2,j=0。 因为
s
t
r
[
i
]
≠
s
t
r
[
j
+
1
]
str[i]\neq str[j+1]
str[i]̸=str[j+1]，且
j
=
0
j=0
j=0，所以
n
e
x
t
[
i
]
=
n
e
x
t
[
2
]
=
0
next[i]=next[2]=0
next[i]=next[2]=0。 因为
s
t
r
[
i
]
=
s
t
r
[
j
+
1
]
str[i]=str[j+1]
str[i]=str[j+1]，匹配成功。所以将
j
j
j 指针右移一位，
n
e
x
t
[
i
]
=
j
+
1
next[i]=j+1
next[i]=j+1。
匹配成功，
j
j
j 右移一位。
匹配失败，令
j
=
n
e
x
t
[
j
]
j=next[j]
j=next[j]，继续判定。
仍然无法配对。因此
n
e
x
t
[
i
]
=
0
next[i]=0
next[i]=0。
luogu P3375
#include<cstdio>
#include<cstdlib>
#include<cstring>
#define reg register
int next
[1000010];
char str1
[1000010],str2
[1000010];
int len1
,len2
,t
=0;
int main(){
memset(next
,0,sizeof(next
));
scanf("%s%s",str1
+1,str2
+1);
len1
=strlen(str1
+1);len2
=strlen(str2
+1);
for(reg
int i
=2;i
<=len2
;++i
){
while(t
>0&&str2
[t
+1]!=str2
[i
]) t
=next
[t
];
if(str2
[t
+1]==str2
[i
]) ++t
;
next
[i
]=t
;
}
t
=0;
for(reg
int i
=1;i
<=len1
;++i
){
while(t
>0&&str2
[t
+1]!=str1
[i
])t
=next
[t
];
if(str2
[t
+1]==str1
[i
]) ++t
;
if(t
==len2
) printf("%d\n",i
-t
+1);
}
for(reg
int i
=1;i
<=len2
;++i
)
printf("%d ",next
[i
]);
}
loj 10043
#include<cstdio>
#include<cstdlib>
#include<cstring>
#define reg register
char str
[1010],s
[1010];
int next
[1010];
int t
=0,l
,len
;
int ans
;
int main(){
do{
scanf("%s",str
+1);
if(str
[1]=='#'&&str
[2]=='\0') break;
scanf("%s",s
+1);
l
=strlen(str
+1);len
=strlen(s
+1);
memset(next
,0,sizeof(next
));
t
=ans
=0;
for(int i
=2;i
<=len
;++i
){
while(t
>0&&s
[t
+1]!=s
[i
]) t
=next
[t
];
if(s
[t
+1]==s
[i
]) ++t
;
next
[i
]=t
;
}
t
=0;
for(int i
=1;i
<=l
;++i
){
while(t
>0&&s
[t
+1]!=str
[i
]) t
=next
[t
];
if(s
[t
+1]==str
[i
]) ++t
;
if(t
==len
) ++ans
,t
=0;
}
printf("%d\n",ans
);
}while(1);
}
