IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> PHP知识库 -> PHP处理最长回文子串 -> 正文阅读

[PHP知识库]PHP处理最长回文子串

目前使用两种方式处理回文子串

解题思路:通过偏移量来计算,当前字符向外扩张,前提字符串存在奇偶性,需要把字符串处理成奇数,在while循环时务必只循环最大偏移量,否则每次都计算的话,循环次数增加,耗时,当输入字符串长度为1000个a,自己写的用时4ms,马拉车6ms,思路主要也是参考马拉车的,自己在简短处理了下
1,自己处理的方式

$s = "babad";
$len = strlen($s);
if ($len < 1) {
    return '';
} elseif ($len <= 2) {
    return $s{0} == $s{1} ? $s : $s{0};
}
$t = 1;
$resCenter = 1;
$val = $s{0};

$symbol = '#';

$s_with_symbol = "\$".$symbol;
for ($i = 0; $i < $len; $i ++) {
    $sub_s = $s{$i} . $symbol;
    $s_with_symbol .= $sub_s;
}

$s_with_symbol_len = strlen($s_with_symbol);

// 执行次数
$co = 0;
for ($i = 1; $i < $s_with_symbol_len; $i++) {
	$co += 1;
    $j = $t;// 偏移量
    while($s_with_symbol{$i - $j} == $s_with_symbol{$i + $j}){
    	$co += 1;
        ++$j;
        if($t < $j){
            $t = $j;
            $resCenter = $i;
        }
    }
}
$val = substr($s, ($resCenter - $t)/2, $t);
return $val;// 总耗时4ms

2,马拉车算法方式

$s_len = strlen($s);
if ($s_len < 1) {
    return '';
} elseif ($s_len <= 2) {
    return $s{0} == $s{1} ? $s : $s{0};
}

$symbol = '#';

$s_with_symbol = "\$" . $symbol;
for ($i = 0; $i < $s_len; $i ++) {
    $sub_s = $s{$i} . $symbol;
    $s_with_symbol .= $sub_s;
}

$p = [];
$mx = 0;
$id = 0;
$resLen = 0;
$resCenter = 0;
$s_with_symbol_len = strlen($s_with_symbol);
$ir=0;
for ($i = 1; $i < $s_with_symbol_len; $i ++) {
    $ir += 1;
    $p[$i] = $mx > $i ? min($p[2 * $id - $i], $mx - $i) : 1;
    while ($s_with_symbol{$i + $p[$i]} == $s_with_symbol{$i - $p[$i]}) {
        ++ $p[$i];
        $ir += 1;
        if ($mx < $p[$i] + $i) {
            $mx = $p[$i] + $i;
            $id = $i;
        }

        if ($resLen < $p[$i]) {
            $resLen = $p[$i];
            $resCenter = $i;
        }
    }
}
retutn substr($s, ($resCenter - $resLen)/2, $resLen - 1);// 总耗时6ms
  PHP知识库 最新文章
Laravel 下实现 Google 2fa 验证
UUCTF WP
DASCTF10月 web
XAMPP任意命令执行提升权限漏洞(CVE-2020-
[GYCTF2020]Easyphp
iwebsec靶场 代码执行关卡通关笔记
多个线程同步执行,多个线程依次执行,多个
php 没事记录下常用方法 (TP5.1)
php之jwt
2021-09-18
上一篇文章      下一篇文章      查看所有文章
加:2021-10-18 17:08:51  更:2021-10-18 17:10:26 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年12日历 -2024/12/28 13:27:44-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码
数据统计