forked from m9rco/algorithm-php
-
Notifications
You must be signed in to change notification settings - Fork 104
Expand file tree
/
Copy pathKmp.php
More file actions
157 lines (141 loc) · 4.86 KB
/
Kmp.php
File metadata and controls
157 lines (141 loc) · 4.86 KB
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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
<?php
/**
* KMP算法
*
* @author Neroxiezi <[email protected]>
* @date 2018/1/11
* @license MIT
* -------------------------------------------------------------
* KMP算法是一种改进的字符串匹配算法
* KMP精要：KMP在进行朴素匹配时，如果发现不匹配字符时，通过对已经匹配的那部分字符串的最大前缀来快速找到下一个模式串需要匹配的位置。
* KMP对模式进行预处理时间复杂度O(m)，匹配时间复杂度O(n)，总的KMP时间复杂度为O(m+n)。
* 参考 字符串匹配的KMP算法 — 阮一峰
*/
// +--------------------------------------------------------------------------
// | 解题方式 | 这儿，可能有用的解决方案
// +--------------------------------------------------------------------------
class KMP
{
public $haystack;
public $needle;
private $_haystackLen;
private $_needleLen;
private $_matchTable;
private $_isMatch;
//构造函数
function __construct($haystack, $needle)
{
$this->haystack = $haystack;
$this->needle = $needle;
//初始化一些参数
$this->_haystackLen = $this->getLen($this->haystack);
$this->_needleLen = $this->getLen($this->needle);
$this->_matchTable = $this->getMatchTable();
$this->_isMatch = false;
}
//类似strpos函数功能
public function strpos()
{
//haystack
$haystackIdx = $matchNum = 0;
while ($haystackIdx <= $this->_haystackLen - $this->_needleLen) {
//needle
$needIdx = 0;
for (; $needIdx < $this->_needleLen; $needIdx++) {
if (strcmp($this->haystack[$haystackIdx], $this->needle[$needIdx]) <> 0) {
if ($matchNum > 0) {
$lastMatchValue = $this->getLastMatchValue($needIdx - 1);
$haystackIdx += $this->getStep($matchNum, $lastMatchValue);
$matchNum = 0;
} else {
$haystackIdx++;
}
break;
} else {
$haystackIdx++;
$matchNum++;
if ($matchNum == $this->_needleLen) {
$this->_isMatch = true;
break;
}
}
}
if ($this->_isMatch == true) {
break;
}
}
return $this->_isMatch ? $haystackIdx - $this->_needleLen : false;
}
//获取字符长度
private function getLen($str)
{
return mb_strlen($str, 'utf-8');
}
//获取部分匹配表
private function getMatchTable()
{
$matchTable = [];
for ($i = 0; $i < $this->_needleLen; $i++) {
$intersectLen = 0;
$nowStr = mb_substr($this->needle, 0, $i + 1, 'utf-8');
$preFixArr = $this->getPreFix($nowStr);
$sufFixArr = $this->getSufFix($nowStr);
if ($preFixArr && $sufFixArr) {
$intersectArr = array_intersect($preFixArr, $sufFixArr);
if (!empty($intersectArr)) {
$intersect = array_pop($intersectArr);
$intersectLen = mb_strlen($intersect, 'utf-8');
}
}
$matchTable[$i] = $intersectLen;
}
return $matchTable;
}
//获取前缀数组
private function getPreFix($str)
{
$outArr = [];
$strLen = $this->getLen($str);
if ($strLen > 1) {
for ($i = 1; $i < $strLen; $i++) {
$outArr[] = mb_substr($str, 0, $i, 'utf-8');
}
}
return $outArr;
}
//获取后缀数组
private function getSufFix($str)
{
$outArr = [];
$strLen = $this->getLen($str);
if ($strLen > 1) {
for ($i = 1; $i < $strLen; $i++) {
$outArr[] = mb_substr($str, $i, null, 'utf-8');
}
}
return $outArr;
}
//计算步长
private function getStep($matchNum, $lastMatchValue)
{
return $matchNum - $lastMatchValue;
}
//获取最后匹配值
private function getLastMatchValue($index)
{
return isset($this->_matchTable[$index]) ? $this->_matchTable[$index] : 0;
}
}
// +--------------------------------------------------------------------------
// | 方案测试 | php `this.php` || PHPStorm -> 右键 -> Run `this.php`
// +--------------------------------------------------------------------------
$str = 'a b a c a a b a c a b a c a b a a b b';
$subStr = 'a b a c a b';
$kmp = new KMP($str, $subStr);
var_dump($kmp->strpos());
$kmp->haystack = 'pull requests';
$kmp->needle = 'sts';
var_dump($kmp->strpos());
$kmp->haystack = 'i love you';
$kmp->needle = 'hate';
var_dump($kmp->strpos());