php 网站开发360,wordpress打电话聊插件,网站建设朋友圈怎么写,网页设计有什么证书数组是一种常用的数据结构#xff0c;高级语言头提供了支持数组的基本操作#xff0c;而且数组也是构成其他数据结构的重要组成。 数组是N个相同元素的构成的占用一块地址连续的内存单元的有限序列。 数组的任一个元素都可以用在数组的位置来表示。 数组与线性表区别#xf…数组是一种常用的数据结构高级语言头提供了支持数组的基本操作而且数组也是构成其他数据结构的重要组成。 数组是N个相同元素的构成的占用一块地址连续的内存单元的有限序列。 数组的任一个元素都可以用在数组的位置来表示。 数组与线性表区别数组符合线性结构的定义。 但是区别是 数组要求占用连续的地址空间线性表的元素是不可分割的数组可以是二维数组数组主要操作是存放和读取数据。 数组的实现机制 通常以字节为内部计数单位。对一个有N个数据元素的一维数组设a0是下标为0的数组元素Loc(a0)的内存单元地址K是每一个数组元素的所需的字节个数则数组中的任一个数据元素ai的内存单元地址为Loc(ai)可由下边公司求出 Loc(ai) Loc(a0) i*K;(0iN) 对于二维数组 M行N列 Loc(ai) Loc(a00) ( i*Nj*;(0iM)(0jN); 串 串是一种线性结构与线性表的不同是串的操作特点是依次操作若干数据元素即一个子串。串可以使用顺序结构和链式结构存储。串的顺序结构存储空间和时间效率更高。模式匹配是串的很重要的一个操作。Brute-Force和KMP算法是两种最经常使用的串的模式匹配算法。 串的基本概念串是有个N0个字符组成的有限序列。一个串中任意个连续的字符组成的子序列称为该串的子串。 串和字符不是一个概念串是长度不定的字符序列的集合。字符只是一个字符。 串的抽象数据类型 串可以是由S0 , ...SN字符的组合。 操作的集合 初始化字符串 赋值字符串 字符串长度 比较字符 插入字符 删除字符 取子串 查找子串 替换子串 C语言用字符数组存储串。串的长度是不定C语言解决长度不定的方法是在串的末尾自动添加一个\0作为字符串的结束标志。 串的存储结构 串的存储结构有顺序存储结构和链式存储结构两种。 串的顺序存储结构 与线性表的存储结构相同可以用一个字符类型的数组存储串值。 在串的顺序存储结构中由于串的长度不定因此要使用一种方法来辨别串的长度一种是固定设置串长度一种是使用\0作为串的结束标志。 串的链式存储结构 串的链式链式结构就是把串值非别存放在构成链表的若干个结点的数据域上。串的链式结构分为单字符点连和块链两种。 单字符链就是一个结点存储一个字符。 块链就是一个结点存储几个字符 串的基本实现方法如同线性表的实现方法。 使用PHP代替 ?php/****串的实现*/header(Content-type: text/html;charsetutf-8);class char { public $size 0; //元素个数而非数组大小 public $arr array(); public $maxsize 10; //数组大小 public function __construct($arr array()) { $this-size count($arr); $this-arr $arr; } public function sizes() { return size;} /** *param int 开始位置 *param string 插入的字符串 *return bool */ public function add($start,$str) { $len strlen($str); if(($start$len) $this-maxsize) { return false;//插入数据超出字符大小 } else { for($i $this-size-1;$i $len;$i--){ $this-arr[$i$len] $this-arr[$i]; } for($i 0;$i$len;$i){ $this-arr[$start$i] $str{$i}; } $this-size $this-size $len; } } /** 0,1,2,3,4,5,6 *删除字符串 *param int 开始位置 *param int 删除的个数 */ public function delete($start,$len) { if(($start$len) $this-maxsize) { return false; } else { for($i$start$len;$i $this-size-1;$i) { $this-arr[$i-$len] $this-arr[$i]; } $this-size $this-size-$len; for($i$this-size-$len;$i $this-size-1;$i) { unset($this-arr[$si]); } } } /** 0,1,2,3,4,5,6 *取字符串 *param int 开始位置 *param int 删除的个数 */ public substr($start,$len) { for($i0;$i$len;$i){ $str.$this-arr[$i$start]; } return $str; } public function getstr() { echo implode(,$this-arr);} /***************串的模式匹配***************/ }$char new char();$char-add(0,1);$char-getstr(); 串的模式匹配 Brute-Force算法 BF算法是普通的模式匹配算法BF算法的思想就是将目标串S的第一个字符与模式串P的第一个字符进行匹配若相等则继续比较S的第二个字符和P的第二个字符若 不相等则比较S的第二个字符和P的第一个字符依次比较下去直到得出最后的匹配结果。 function BF($str,$t) { for($i0;$istrlen($str);$i) { for($j0;$jstrlen($t);$j) { if($str{$i}$t{$j}) {$i;} else { echo .$i.-.$j.;$i $i-$j; break;} } if($jstrlen($t)) return true; } return Flase; } function BF2($str,$t) { $i$j0; while($istrlen($str)) { $j0; while($str{$i} $t{$j} $jstrlen($t)) { $i; $j; } if($jstrlen($t)) return true; } return Flase; } KMP算法是对BF算法的优化 ?phpfunction indexNext($str){ $k 0; //相同字符的位数 $j1; $nexts[0] -1; //是为了匹配当一个模式字符不予串匹配时的情况 $nexts[1] 0; //当第二字符不匹配时 直接比较第一个字符 while($jstrlen($str)) { if($str{$j} $str{$k}) { //出现相同字符时 $nexts[$j1] $k1; $j; $k; } else if($k0) { //未出现相同字符 且前边也未出现相同字符时 $nexts[$j1] 0; $j; } else { //前边有相同字符依次用当前字符比较是否与以前字符相同 $k $nexts[$k]; } } return $nexts;}function KMP($str,$t) { $nexts indexNext($t); print_r($nexts); $i 0;$j0; $k 0; while($istrlen($str) $j strlen($t)) { $k ; if($j -1 || $str{$i} $t{$j}) {//是为了匹配当一个模式字符不予串匹配时的情况及当$str{$i} $t{$j} $i;$j; } else { //当$str{$i} $t{$j} 算出 真子串中相同的部分 真子串中相同的部分不用在比较 echo $i.-.$j.*; $j $nexts[$j]; } if($jstrlen($t)) {echo $k;return true;} } return false; }echo KMP(BBC ABCDAB ABCDABCDABDE,ABCDABD);print_R(indexNext(AAABCDAAABD)); 请问广大牛人这样实习KMP算法对吗转载于:https://www.cnblogs.com/phplhs/p/4340793.html