分类: 其他平台
2015-06-08 15:44:07
个人觉得这篇文章是网上的介绍有关KMP算法更让人容易理解的文章了,确实说得很“详细”,耐心地把它看完肯定会有所收获的~~,另外有关模式函数值next[i]确实有很多版本啊,在另外一些面向对象的算法描述书中也有失效函数 f(j)的说法,其实是一个意思,即next[j]=f(j-1)+1,不过还是next[j]这种表示法好理解啊:
KMP字符串模式匹配详解
下标
|
0
|
1
|
2
|
3
|
4
|
T
|
a
|
b
|
c
|
a
|
c
|
next
|
-1
|
0
|
0
|
-1
|
1
|
下标
|
0
|
1
|
2
|
3
|
4
|
T
|
a
|
b
|
c
|
a
|
b
|
next
|
-1
|
0
|
0
|
-1
|
0
|
下标
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
T
|
a
|
b
|
a
|
b
|
c
|
a
|
a
|
b
|
c
|
next
|
-1
|
0
|
-1
|
0
|
2
|
-1
|
1
|
0
|
2
|
下标
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
T
|
a
|
b
|
C
|
a
|
b
|
C
|
a
|
d
|
next
|
-1
|
0
|
0
|
-1
|
0
|
0
|
-1
|
4
|
下标
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
T
|
a
|
d
|
C
|
a
|
d
|
C
|
a
|
d
|
next
|
-1
|
0
|
0
|
-1
|
0
|
0
|
-1
|
0
|
下标
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
T
|
a
|
b
|
a
|
b
|
c
|
a
|
a
|
b
|
c
|
(1) next
|
-1
|
0
|
-1
|
0
|
2
|
-1
|
1
|
0
|
2
|
(2) next
|
-1
|
0
|
0
|
1
|
2
|
0
|
1
|
1
|
2
|
(3) next
|
0
|
1
|
0
|
1
|
3
|
0
|
2
|
1
|
3
|
下标
|
0
|
1
|
2
|
3
|
4
|
T
|
a
|
b
|
c
|
A
|
c
|
(1)next
|
-1
|
0
|
0
|
-1
|
1
|
(2)next
|
-1
|
0
|
0
|
0
|
1
|
下标
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
T
|
a
|
d
|
C
|
a
|
d
|
C
|
a
|
d
|
(1)next
|
-1
|
0
|
0
|
-1
|
0
|
0
|
-1
|
0
|
(2)next
|
-1
|
0
|
0
|
0
|
1
|
2
|
3
|
4
|