PHP实现的字符串匹配算法示例【sunday算法】

本文实例讲述了PHP实现的字符串匹配算法————sunday算法。分享给大家供大家参考，具体如下：

Sunday算法是Daniel M.Sunday于1990年提出的字符串模式匹配。其核心思想是:在匹配过程中，模式串发现不匹配时，算法能跳过尽可能多的字符以进行下一步的匹配，从而提高了匹配效率。

<?php
/*
 *@param $pattern 模式串
 *@param $text 待匹配串
 */
function mySunday($pattern = '',$text = ''){
  if(!$pattern || !$text) return false;
  $pattern_len = mb_strlen($pattern);
  $text_len = mb_strlen($text);
  if($pattern_len >= $text_len) return false;
  $i = 0;
  for($i = 0; $i < $pattern_len; $i++){ //组装以pattern中的字符为下标的数组
    $shift[$pattern[$i]] = $pattern_len - $i;
  }
  while($i <= $text_len - $pattern_len){
    $nums = 0;   //匹配上的字符个数
    while($pattern[$nums] == $text[$i + $nums]){
      $nums++;
      if($nums == $pattern_len){
        return "The first match index is $i\n";
      }
    }
    if($i + $pattern_len < $text_len && isset($shift[$text[$i + $pattern_len]])){ //判断模式串后一位字符是否在模式串中
      $i += $shift[$text[$i + $pattern_len]];   //对齐该字符
    }else{
      $i += $pattern_len;   //直接滑动pattern_len位
    }
  }
}
$text = "I am testing mySunday on sunday!";
$pattern = "sunday";
echo mySunday($pattern,$text);

运行结果：

The first match index is 25

更多关于PHP相关内容感兴趣的读者可查看本站专题：《PHP数据结构与算法教程》、《php程序设计算法总结》、《php字符串(string)用法总结》、《PHP数组(Array)操作技巧大全》、《PHP常用遍历算法与技巧总结》及《PHP数学运算技巧总结》

希望本文所述对大家PHP程序设计有所帮助。

赞 (0)

相关推荐

  • PHP实现的最大正向匹配算法示例

    本文实例讲述了PHP实现的最大正向匹配算法.分享给大家供大家参考,具体如下: 正向最大匹配算法:从左到右将待分词文本中的几个连续字符与词表匹配,如果匹配上,则切分出一个词.但这里有一个问题:要做到最大匹配,并不是第一次匹配到就可以切分的 . 函数中包含三个参数: $query   查询词 $dict    词典 $max_len 最大长度(这里默认值设置为15) 词典示例: $dict = array( '我们'=>'我们', '脚本下载'=>'脚本下载', 'JS编程'=>'JS编程'

  • php中最简单的字符串匹配算法

    本文实例讲述了php中最简单的字符串匹配算法.分享给大家供大家参考.具体实现方法如下: 复制代码 代码如下: <?php /* 最简单字符串匹配算法php实现方式   T: ababcabc P: abc   0.          1.          2. ababcabc    ababcabc    ababcabc |||          |||          ||| abc          abc          abc (X)          (X)         

  • PHP实现找出数组中出现次数超过数组长度一半的数字算法示例

    本文实例讲述了PHP实现找出数组中出现次数超过数组长度一半的数字算法.分享给大家供大家参考,具体如下: <?php * 算法要求:数组中有一个数字出现的次数超过了数组长度的一半,找出这个数字. * * 算法分析:我们需要计算数组中每个数字的出现次数.在PHP中我们可以使用in_array函数 * 来判断一个元素是否出现在数组中.比如数组中含有1,2,3三个元素,我们要判断1是否存在 * 可以使用in_array(1,$array)来判断,但是这样只能判断1出现了一次,因为对于含有数组 * 元素1

  • python中文分词教程之前向最大正向匹配算法详解

    前言 大家都知道,英文的分词由于单词间是以空格进行分隔的,所以分词要相对的容易些,而中文就不同了,中文中一个句子的分隔就是以字为单位的了,而所谓的正向最大匹配和逆向最大匹配便是一种分词匹配的方法,这里以词典匹配说明. 最大匹配算法是自然语言处理中的中文匹配算法中最基础的算法,分为正向和逆向,原理都是一样的. 正向最大匹配算法,故名思意,从左向右扫描寻找词的最大匹配. 首先我们可以规定一个词的最大长度,每次扫描的时候寻找当前开始的这个长度的词来和字典中的词匹配,如果没有找到,就缩短长度继续寻找,直

  • PHP基于二分法实现数组查找功能示例【循环与递归算法】

    PHP基于二分法实现数组查找功能示例【循环与递归算法】

    本文实例讲述了PHP基于二分法实现数组查找功能.分享给大家供大家参考,具体如下: 二分法.分别使用while循环的方法和递归调用的方法. <?php // 二分法的使用数组必须是有序的,或升序,或降序 $arr = array( 1, 3, 5, 7, 9, 13 ); // 递归调用(相比较好理解 function bsearch_r($v, $arr, $low, $high){ if ($low > $high) {// 先判断结束条件 return -1; } $i = intval(

  • PHP实现机器学习之朴素贝叶斯算法详解

    本文实例讲述了PHP实现机器学习之朴素贝叶斯算法.分享给大家供大家参考,具体如下: 机器学习已经在我们的生活中变得随处可见了.比如从你在家的时候温控器开始工作到智能汽车以及我们口袋中的智能手机.机器学习看上去已经无处不在并且是一个非常值得探索的领域.但是什么是机器学习呢?通常来说,机器学习就是让系统不断的学习并且对新的问题进行预测.从简单的预测购物商品到复杂的数字助理预测. 在这篇文章我将会使用朴素贝叶斯算法Clasifier作为一个类来介绍.这是一个简单易于实施的算法,并且可给出满意的结果.但

  • php 二维数组快速排序算法的实现代码

    php 二维数组快速排序算法的实现代码 二维数组排序算法与一维数组排序算法基本理论都是一样,都是通过比较把小的值放在左变的数组里,大的值放在右边的数组里在分别递归. 实例代码: <?php class Bubble { private function __construct() { } private static function sortt($data) { if (count ( $data ) <= 1) { return $data; } $tem = $data [0]['sco

  • PHP基于回溯算法解决n皇后问题的方法示例

    本文实例讲述了PHP基于回溯算法解决n皇后问题的方法.分享给大家供大家参考,具体如下: 这里对于n皇后问题就不做太多的介绍,相关的介绍与算法分析可参考前面一篇C++基于回溯法解决八皇后问题. 回溯法的基本做法是搜索,或是一种组织得井井有条的,能避免不必要搜索的穷举式搜索法.这种方法适用于解一些组合数相当大的问题. 回溯法在问题的解空间树中,按深度优先策略,从根结点出发搜索解空间树.算法搜索至解空间树的任意一点时,先判断该结点是否包含问题的解.如果肯定不包含,则跳过对该结点为根的子树的搜索,逐层向

  • 基于PHP实现栈数据结构和括号匹配算法示例

    本文实例讲述了基于PHP实现栈数据结构和括号匹配算法.分享给大家供大家参考,具体如下: 栈,体现的是后进先出,即LIFO.队列,体现的是先进先出,即FIFO. 栈操作: array_pop() //尾出 array_push() //尾进 或 array_shift()//头进 array_unshift()//头出 用例:验证一个数学算式是否正确,比如{2*3[x*y+5+m*(i-j)/3]+k*(4+(t+9))}. 分析:对于一个算式的正确与否,就是体现在,各种括号的匹配上,括号完全匹配

  • PHP实现的贪婪算法实例

    本文实例讲述了PHP实现的贪婪算法.分享给大家供大家参考,具体如下: 背景介绍:贪婪算法与数据结构知识库算法可以说是离我们生活最近的一种算法,人总是贪婪的嘛,所以这种算法的设计是很符合人性的.之所以这么说,是因为人们会在生活中有意无意的使用贪婪算法来解决问题.最常见的就是找零钱了,每个人都没学过该怎么找零钱,但在所有面额的钱都充足时,每个人都会找出同样组合来凑够需要的钱.其实这里面就是贪婪算法在起作用. 设计思路:贪婪法的设计思路可以从两方面来理解,即直观上和数学上.从直观上理解贪婪算法就是用最

  • PHP实现的折半查询算法示例

    PHP实现的折半查询算法示例

    本文实例讲述了PHP实现的折半查询算法.分享给大家供大家参考,具体如下: 什么是折半查询算法?具体文字描述自己百度.直接上代码: <?php header("Content-type: text/html; charset=utf-8"); /* 折半查询算法--不用递归 */ function qSort($data = array(), $x = 0){ $startIndex = 0; // 开始索引 $endIndex = count($data) - 1; // 结束索

随机推荐