Sunday 算法（尽可能的移动最大长度）
Sunday算法是从前往后匹配，在匹配失败时关注的是文本串中参加匹配的最末位字符的下一位字符
- 如果该字符没有在主模式字符串中出现则跳过，移动位 = 匹配字符串长度 + 1
- 该字符在主模式字符串中出现，
1)移动位 = 该字符在模式串中最后出现位置距末端长度 + 1
2)移动位 = 模式串长度 - 该字符在模式串中最后出现位置
文本串第1个字符 s != 模式串第1个字符 e，那么关注文本串中参加匹配的未位字符下一个字符： a
a 在 ea 字符串的最后一位，则移动位= 0 + 1 = 2（模式串长度） - 1（a 在模式串最后出现位置）= 1
模式串向右移动 1 位，使上下文的 a 对齐
匹配成功
代码实现
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
| <?php
namespace Patterns\Algorithm;
/**
* 如果该字符没有在主模式字符串中出现则跳过，移动位 = 匹配字符串长度 + 1
* 该字符在主模式字符串中出现，
1)移动位 = 该字符在模式串中最后出现位置距末端长度 + 1
2)移动位 = 模式串长度 - 该字符在模式串中最后出现位置
* Class Sunday
* @package Patterns\Algorithm
*/
class Sunday
{
public $_needleLen;
public $_haystackLen;
public $_table;
/**
* 返回 -1 表示无法匹配，否则返回首次出现位置
*
* @param string $haystack
* @param string $needle
* @return int
*/
public function strpos(string $haystack, string $needle):int
{
$this->_haystackLen = strlen($haystack);
$this->_needleLen = strlen($needle);
if($this->_needleLen > $this->_haystackLen){
return null;
}
$this->prefixTable($needle);
$p = $this->_haystackLen - $this->_needleLen;
$s = 0;
while ($s <= $p){
$j = 0;
while ($haystack[$s + $j] == $needle[$j]){
$j += 1;
if($j == $this->_needleLen){
return $s;
}
}
$haystackIndex = $s + $this->_needleLen;
if(!isset($haystack[$haystackIndex]))
break;
$hIndexText = $haystack[$haystackIndex];
$s += (isset($this->_table[$hIndexText]) ? $this->_table[$hIndexText] : $this->_needleLen);
}
return -1;
}
/**
* 匹配所有出现位置
* @param string $haystack
* @param string $needle
* @return array
*/
public function strapos(string $haystack, string $needle):array
{
$this->_haystackLen = strlen($haystack);
$this->_needleLen = strlen($needle);
if($this->_needleLen > $this->_haystackLen){
return null;
}
$this->prefixTable($needle);
$p = $this->_haystackLen - $this->_needleLen;
$s = 0;
$pos = [];
while ($s <= $p){
$j = 0;
while (isset($needle[$j]) && $haystack[$s + $j] == $needle[$j]){
$j += 1;
if($j == $this->_needleLen){
array_push($pos, $s);
}
}
$haystackIndex = $s + $this->_needleLen;
if(!isset($haystack[$haystackIndex]))
break;
$hIndexText = $haystack[$haystackIndex];
$s += (isset($this->_table[$hIndexText]) ? $this->_table[$hIndexText] : $this->_needleLen);
}
return $pos;
}
/**
* 模式串字符表
* @param string $needle
*/
public function prefixTable(string $needle)
{
for($i=0; $i < $this->_needleLen; $i++){
//字符最后出现的位置距末端长度：字符串长度 - 字符当前位置
$this->_table[$needle[$i]] = $this->_needleLen - $i;
}
}
}
$haystack = 'search title.';
$needle = 'w';
$obj = new Sunday();
$index = $obj->strpos($haystack, $needle);
echo $index . PHP_EOL;
var_export($obj->strapos($haystack, $needle));
echo strpos($haystack, $needle) . PHP_EOL;
|