每一个算法，都是基于很简单的道理，不断地增加条件，限制，让它符合心意。也就没有其他的东西了。
ＫＭＰ：
也就是我自己写的一个思路，肯定我讲不清楚，我还没有那么通透，只能记录下我现在的一个思路，而且也没必要测试。
直接上代码
|
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
76
77
78
79
|
<?php
//基本KMP算法
//看来真的不能解释，本来我还想着解释下一下算法的改进过程发现需要图形示意，算了
//在串S中找串T
//我么为了省事,研究T的特点，每个字符在T中特点，主要是相似程度
//我拿着T去和S比对，肯定有一部分是一样的，突然不一样了，
//问题就是在这个一样的地方，可以节省步骤，“我”代指T中接下来要去匹配的串
//我在T中和相似，你都和S不一样了，我再去比较，不是费事吗，真的是废物了
//怎么标记我在T中的特点，其实就是跳转信息，我想让你略过我的位置，直接过，仅此而已。
//优化只发生在T中的小循环
//这就引入了next数组，记录省事的条状信息。在next几处上发现有点不够完美，还可以更省事
//这就引入了nextVal数组
//结束，哈哈
//就是计算出来那个最初的next,来分析T的特征
function
get_next(
$string
=
''
){
$i
=0;
$j
=0;
$next
=
array
();
$next
[1] = 0;
while
(
$i
<
strlen
(
$string
)){
if
(
$j
==0 ||
substr
(
$string
,
$i
,1)==
substr
(
$string
,
$j
,1)){
++
$i
;
++
$j
;
$next
[
$i
]=
$j
;
}
else
{
$j
=
$next
[
$j
];
}
}
return
$next
;
}
//改进，正式的话，上面那个函数就不要看了，只是体现思路
//改进的意思就是大部分一模一样
function
get_nextVal(
$string
=
''
){
$i
=0;
$j
=0;
$nextval
=
array
();
$nextval
[0] = 0;
while
(
$i
<
strlen
(
$string
)){
if
(
$j
==0 ||
substr
(
$string
,
$i
,1)==
substr
(
$string
,
$j
,1)){
++
$i
;
++
$j
;
if
(
substr
(
$string
,
$i
,1)!=
substr
(
$string
,
$j
,1)){
$nextval
[
$i
]=
$j
;
}
else
{
$nextval
[
$i
]=
$nextval
[
$j
];
}
}
else
{
$j
=
$nextval
[
$j
];
}
}
return
$nextval
;
}
funvtion index_KMP($Ｔ,$Ｓ){
$i
=
$pos
;
$j
=0;
$nextVal
=
array
();
$nextVal
=get_nextVal(
$T
);
//.....后面先不写了
while
(
$i
<
strlen
(
$S
)&&
$j
<
strlen
(
$T
))){
if
(
$j
==0 ||
substr
(
$string
,
$i
,1)==
substr
(
$string
,
$j
,1)){
++
$i
;
++
$j
;
}
else
{
$j
=nextVal[
$j
];
}
}
if
(
$j
>
strlen
(
$T
)){
return
$i
-
strlen
(
$T
);
}
else
{
return
0;
}
}
|
注：这是一个不复杂的思路，人家研究出来的就是很多人都可以理解的。如何运用出去那才是卖油翁的熟能生巧。
注：具体的思路推导，请参考其他大牛写的文档。
本文转自 jackdongting 51CTO博客，原文链接:http://blog.51cto.com/10725691/1949687
