PHP实现KMP算法

记得大二的时候,就学过KMP算法,当时还觉得这个算法很有趣。今天,做字符串匹配,却没想到要用它,而用了较笨的方法求解,时间复杂度为O(m*n)。下面重温一下KMP算法。

KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现,因此人们称它为克努特——莫里斯——普拉特操作(简称KMP算法)。KMP算法的关键是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next()函数,函数本身包含了模式串的局部匹配信息。时间复杂度O(m+n)。

KMP算法的具体步骤如下:

1.

首先,字符串”BBC ABCDAB ABCDABCDABDE”的第一个字符与搜索词”ABCDABD”的第一个字符,进行比较。因为B与A不匹配,所以搜索词后移一位。

更多 »

PHP 5.2、5.3、5.4、5.5、5.6 对比以及功能详解

php5.2.x php5.3.x php5.4.x php5.5.x php5.6.x 对比详解

截至目前(2014.2), PHP 的最新稳定版本是 PHP5.5, 但有差不多一半的用户仍在使用已经不在维护 [注] 的 PHP5.2, 其余的一半用户在使用 PHP5.3 [注].
因为 PHP 那“集百家之长”的蛋疼语法,加上社区氛围不好,很多人对新版本,新特征并无兴趣。
本文将会介绍自 PHP5.2 起,直至 PHP5.6 中增加的新特征。
  • PHP5.2 以前:autoload, PDO 和 MySQLi, 类型约束
  • PHP5.2:JSON 支持
  • PHP5.3:弃用的功能,匿名函数,新增魔术方法,命名空间,后期静态绑定,Heredoc 和 Nowdoc, const, 三元运算符,Phar
  • PHP5.4:Short Open Tag, 数组简写形式,Traits, 内置 Web 服务器,细节修改
  • PHP5.5:yield, list() 用于 foreach, 细节修改
  • PHP5.6: 常量增强,可变函数参数,命名空间增强

PHP5.2以前

(2006前)
顺便介绍一下 PHP5.2 已经出现但值得介绍的特征。

autoload

大家可能都知道 __autoload() 函数,如果定义了该函数,那么当在代码中使用一个未定义的类的时候,该函数就会被调用,你可以在该函数中加载相应的类实现文件,如:

function __autoload($classname){    require_once(“{$classname}.php”)}

但该函数已经不被建议使用,原因是一个项目中仅能有一个这样的 __autoload() 函数,因为 PHP 不允许函数重名。但当你使用一些类库的时候,难免会出现多个 autoload 函数的需要,于是 spl_autoload_register() 取而代之:

spl_autoload_register(function($classname){    require_once(“{$classname}.php”)});

spl_autoload_register() 会将一个函数注册到 autoload 函数列表中,当出现未定义的类的时候,SPL [注] 会按照注册的倒序逐个调用被注册的 autoload 函数,这意味着你可以使用 spl_autoload_register() 注册多个 autoload 函数.
注:SPL: Standard PHP Library, 标准 PHP 库, 被设计用来解决一些经典问题(如数据结构).

PDO 和 MySQLi

即 PHP Data Object, PHP 数据对象,这是 PHP 的新式数据库访问接口。
按照传统的风格,访问 MySQL 数据库应该是这样子:

// 连接到服务器,选择数据库$conn = mysql_connect(“localhost”, “user”, “password”);mysql_select_db(“database”);// 执行 SQL 查询$type =$_POST['type'];$sql = “SELECT * FROM `table` WHERE `type` = {$type}”;$result = mysql_query($sql);// 打印结果while($row =mysql_fetch_array($result, MYSQL_ASSOC)){    foreach($row as $k => $v)        print “{$k}: {$v}\n”;}// 释放结果集,关闭连接mysql_free_result($result);mysql_close($conn);

为了能够让代码实现数据库无关,即一段代码同时适用于多种数据库(例如以上代码仅仅适用于MySQL),PHP 官方设计了 PDO.
除此之外,PDO 还提供了更多功能,比如:
  • 面向对象风格的接口
  • SQL预编译(prepare), 占位符语法
  • 更高的执行效率,作为官方推荐,有特别的性能优化
  • 支持大部分SQL数据库,更换数据库无需改动代码
上面的代码用 PDO 实现将会是这样:

// 连接到数据库$conn = new PDO(“mysql:host=localhost;dbname=database”, “user”, “password”);// 预编译SQL, 绑定参数$query = $conn->prepare(“SELECT * FROM `table` WHERE `type` = :type”);$query->bindParam(“type”, $_POST['type']);// 执行查询并打印结果foreach($query->execute() as $row){    foreach($row as $k => $v)        print “{$k}: {$v}\n”;}

PDO 是官方推荐的,更为通用的数据库访问方式,如果你没有特殊需求,那么你最好学习和使用 PDO.
但如果你需要使用 MySQL 所特有的高级功能,那么你可能需要尝试一下 MySQLi, 因为 PDO 为了能够同时在多种数据库上使用,不会包含那些 MySQL 独有的功能。
MySQLi 是 MySQL 的增强接口,同时提供面向过程和面向对象接口,也是目前推荐的 MySQL 驱动,旧的C风格 MySQL 接口将会在今后被默认关闭。
MySQLi 的用法和以上两段代码相比,没有太多新概念,在此不再给出示例,可以参见 PHP 官网文档 [注]。

更多 »

体验型主机免费使用活动

体验型主机是完全基于IPv6访问主机空间。这意味着带有IPv6的校园网用户可以通过IPv6访问网站,而IPv4外界网络将不会访问到网站。这样做,可以减少网站被恶意发广告、外链,还可以避免网站受到IPv4流量的攻击等问题。体验型主机的免费推出,是校园网用户的福音。

体验型主机主要有三类产品,它们分别是HTML空间、PHP空间和JSP空间,其中PHP空间和JSP空间均支持HTML网页的访问。该产品的特点及说明如下:
1.该产品不支持自助绑定域名,只允许使用系统默认提供的三级域名访问网站;
2.该产品的空间容量较小,不允许建网站,只提供给学习制作网页的人使用;
3.JAVA空间需要联系客服添加JSP网页的访问支持;
4.JAVA空间可以向客服申请一个带8080端口访问的独立的IPv6地址
5.该产品不提供数据备份保障,请使用者自行将数据本地备份;
6.该产品不支持退款服务;
7.本站享有最终解释权。

更多 »

php开启GD库实现显示图片验证码

安装完php+mysql环境,默认是没有开启gd库的,开启方法:
1、打开web服务器安装目录下的php.ini文件(有可能在其他路径);
2、去掉;extension=php_gd.dll或;extension=php_gd2.dll前的“;”(开启GD库扩展);
3、最后,重启web服务器即可。

 

简单来说,就是找到PHP的配置文件php.ini,去掉被禁用扩展前面的分号。

Copyright © All Rights Reserved · 菁菁博客 Since 2012 · Proudly powered by WordPress