博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
PHP 字符串匹配算法 Sunday算法
阅读量:5876 次
发布时间:2019-06-19

本文共 1834 字,大约阅读时间需要 6 分钟。

搜索文本 text = "my testing algorithm in test"

模式 pattern = "test"

Sunday算法的关键点在于

1.设定一个匹配位移映射 shift[],这个shift[]映射关系必须按从左到右的顺序简历,例如pattern = "test",注意到此处有2个t,那么建立出来的位移映射是 shift[] = Array ( [t] => 1 [e] => 3 [s] => 2 ),而如果不是从左到右,是从右到左的建立映射,就会变成 shift[] = Array ( [t] => 4 [e] => 3 [s] => 2),这样到时候匹配就无法得到正确结果

2.根据当前比对字符串的下一个字符来确定位移长度,如下图

第一次比较的时候,如图1,第一个字符“m”就和“t”不一样,那就查找比patter长1位的text中的字符,为“e”,然后查找映射表,e => 3,接下来把pattern向后移动3位,就到了,图2中的位置,再从“t”开始比较,发现匹配到了继续往后,看text中比pattern长1的那个字符,为“i”,此时发现映射表中没有“i”,则直接将pattern向后移动pattern_size位,就到了图3,然后重复前面的过程,直到比较到text_size - patter_size为坐标的那个字符

 

下面是代码:

1 
4 [e] => 6 [s] => 5 [i] => 3 [n] => 2 [g] => 1 )12 #而如果不是从左到右,是从右到左的建立映射,就会变成 shift[] = Array ( [t] => 7 [e] => 6 [s] => 5 [i] => 3 [n] => 2 [g] => 1 ),这样到时候匹配就无法得到正确结果13 for ($i = 0; $i < $patt_size; $i++) {14 $shift[$patt[$i]] = $patt_size - $i;15 }16 17 $i = 0;18 $limit = $text_size - $patt_size; #需要开始匹配的最后一个字符坐标19 while ($i <= $limit) {20 $match_size = 0; #当前已匹配到的字符个数21 #从i开始匹配字符串22 while ($text[$i + $match_size] == $patt[$match_size]) {23 $match_size++;24 if ($match_size == $patt_size) {25 echo "Match index: {
$i}
";26 break;27 }28 }29 30 $shift_index = $i + $patt_size; #在text中比pattern的多一位的字符坐标31 if ($shift_index < $text_size && isset($shift[$text[$shift_index]])) {32 $i += $shift[$text[$shift_index]];33 } else {34 #如果映射表中没有这个字符的位移量,直接向后移动patt_size个单位35 $i += $patt_size;36 }37 }38 }39 40 $text = "my testing algorithm test";41 $patt = "test";42 43 sunday($patt, $text);44 ?>

 

 

Match index: 3 

Match index: 21

转载地址:http://jfzix.baihongyu.com/

你可能感兴趣的文章
python入门系列:Python socket编程
查看>>
三年内拿下众多500强客户,观远数据这家新兴BI厂商有哪些大杀器?
查看>>
Redux + (RxKotlin | RxSwift) =很棒的本地移动应用程序
查看>>
蛋花花浅谈人工智能主要应用于哪些方面
查看>>
MIME类型大全
查看>>
我的友情链接
查看>>
global_name启用以及修改规则
查看>>
我的友情链接
查看>>
我的友情链接
查看>>
Spring Cache抽象详解
查看>>
微信JSSDK上传图片
查看>>
java集合类深入分析之Queue篇(1)
查看>>
bond的7种模式原理
查看>>
C语言的简单函数定义与调用
查看>>
二维码
查看>>
7-24
查看>>
spring中的JdbcTemplate简单记录
查看>>
pygame连载
查看>>
寒冰linux视频教程笔记12 计划任务
查看>>
在C盘上安装安装Windows Server 2008
查看>>