当前位置: 首页 > news >正文

PHP 求解两字符串所有公共子序列及最长公共子序列 支持多字节字符串


/*** 获取两字符串所有公共子序列【不连续的】 例:abc ac => ac** @param string $str1 字符串1* @param string $str2 字符串2** @return array*/
function public_sequence(string $str1, string $str2): array
{$data = [[-1, -1, '', 0, '']]; // 子序列容器【横坐标 纵坐标 当前子序列 长度 足迹】$arr  = []; // 动态规划容器$arr1 = mb_str_split($str1);$arr2 = mb_str_split($str2);$len1 = count($arr1);$len2 = count($arr2);// 动态规划for ($y = 0; $y < $len2; ++$y) {for ($x = 0; $x < $len1; ++$x) {$arr[$y][$x] = $arr1[$x] === $arr2[$y] ? 1 : 0;e($arr[$y][$x], 'n'); // 打印数据}e(); // 换行}// 寻找所有子序列$len = $len1 > $len2 ? $len1 : $len2;for ($i = 0; $i < $len; ++$i) {foreach ($data as &$value) {++$value[0]; // 横坐标++$value[1]; // 纵坐标$len = $value[3] + 1; // 长度// 纵坐标固定,横坐标增加,检验横行数据for ($x = $value[0]; $x < $len1; ++$x) {if ($value[1] >= $len2) break;if ($arr[$value[1]][$x] === 1) $data[] = [$x, $value[1], $value[2] . $arr1[$x], $len, $value[4] . '(' . $x . ',' . $value[1] . ')'];}// 横坐标固定,纵坐标增加,检验纵行数据for ($y = $value[1] + 1; $y < $len2; ++$y) {if ($value[0] >= $len1) break;if ($arr[$y][$value[0]] === 1) $data[] = [$value[0], $y, $value[2] . $arr2[$y], $len, $value[4] . '(' . $value[0] . ',' . $y . ')'];}}}return $data;
}/*** 获取两字符串所有最长公共子序列 注意:最长字符串子序列可能有多个** @param string $str1 字符串1* @param string $str2 字符串2** @return array*/
function long_public_sequence(string $str1, string $str2): array
{$data = []; // 最长子序列容器$tmp  = []; // 临时子序列容器$len = 0; // 最长子序列长度// 获取所有公共子序列$subsequence = public_sequence($str1, $str2);// 找到最长子序列长度及个数foreach ($subsequence as $value) {if ($len > $value[3]) continue;$len = $value[3];$tmp[] = $value;}// 根据最长子序列长度筛选数据foreach ($tmp as $value) {if ($len === $value[3]) $data[] = $value;}return $data;
}$str1 = '安保处的';
$str2 = '安保的';v(public_sequence($str1, $str2));
vd(long_public_sequence($str1, $str2));

执行结果:

相关文章:

PHP 求解两字符串所有公共子序列及最长公共子序列 支持多字节字符串

/*** 获取两字符串所有公共子序列【不连续的】 例&#xff1a;abc ac > ac** param string $str1 字符串1* param string $str2 字符串2** return array*/ function public_sequence(string $str1, string $str2): array {$data [[-1, -1, , 0, ]]; // 子序列容器【横坐标 …...

linux内核bitmap之setbit汇编实现

内核版本&#xff1a;kernel 0.12 首先看一段代码&#xff0c;下面这段代码来自内核版本0.12的mm/swap.c中&#xff1a; // mm/swap.c #define bitop(name,op) \static inline int name(char * addr,unsigned int nr) \ { \int __res; \__asm__ __volatile__("bt" …...

Golang设计模式

Golang设计模式 Golang设计模式简介Golang工厂设计模式Golang单例设计模式Golang抽象工厂设计模式Golang建造者模式 (Builder Pattern)Golang 原型模式(Prototype Pattern)Golang适配器模式Golang 桥接模式&#xff08;Bridge Pattern&#xff09;Golang装饰器模式(Decorator …...

leetcode151. 反转字符串中的单词

题目&#xff1a;leetcode151. 反转字符串中的单词 描述&#xff1a; 给你一个字符串 s &#xff0c;请你反转字符串中 单词 的顺序。 单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。 返回 单词 顺序颠倒且 单词 之间用单个空格连接的结…...

【BASH】回顾与知识点梳理(十七)

【BASH】回顾与知识点梳理 十七 十七. 什么是 Shell scripts17.1 干嘛学习 shell scripts自动化管理的重要依据追踪与管理系统的重要工作简单入侵检测功能连续指令单一化简易的数据处理跨平台支持与学习历程较短 17.2 第一支 script 的撰写与执行撰写第一支 script 17.3 撰写 s…...

时序预测-Informer简介

文章目录 Informer介绍1. Transformer存在的问题2. Informer研究背景3. Informer 整体架构3.1 ProbSparse Self-attention3.2 Self-attention Distilling3.3 Generative Style Decoder 4. Informer的实验性能5. 相关资料 Informer介绍 1. Transformer存在的问题 Informer实质…...

2023牛客第七场补题报告C F L M

2023牛客第七场补题报告C F L M C-Beautiful Sequence_2023牛客暑期多校训练营7 (nowcoder.com) 思路 观察到数组一定是递增的&#xff0c;所以从最高位往下考虑每位的1最多只有一个&#xff0c;然后按位枚举贪心即可。 代码 #include <bits/stdc.h> using namespac…...

Android使用kotlin+协程+room数据库的简单应用

前言&#xff1a;一般主线程&#xff08;UI线程&#xff09;中是不能执行创建数据这些操作的&#xff0c;因为等待时间长。所以协程就是为了解决这个问题出现。 第一步&#xff1a;在模块级的build.gradle中引入 id com.android.application// roomid kotlin-androidid kotlin…...

Kubernetes pod调度约束[亲和性 污点] 生命阶段 排障手段

调度约束 Kubernetes 是通过 List-Watch 的机制进行每个组件的协作&#xff0c;保持数据同步的&#xff0c;每个组件之间的设计实现了解耦。 用户是通过 kubectl 根据配置文件&#xff0c;向 APIServer 发送命令&#xff0c;在 Node 节点上面建立 Pod 和 Container。 APIServer…...

Matlab实现模拟退火算法(附上多个完整源码)

模拟退火算法&#xff08;Simulated Annealing&#xff09;是一种全局优化算法&#xff0c;其基本思想是通过模拟物理退火过程来寻找最优解。该算法可以应用于各种优化问题&#xff0c;如函数优化、组合优化、图形优化等。 文章目录 步骤简单案例完整仿真源码下载 步骤 在Mat…...

前后端分离------后端创建笔记(03)前后端对接(上)

本文章转载于【SpringBootVue】全网最简单但实用的前后端分离项目实战笔记 - 前端_大菜007的博客-CSDN博客 仅用于学习和讨论&#xff0c;如有侵权请联系 源码&#xff1a;https://gitee.com/green_vegetables/x-admin-project.git 素材&#xff1a;https://pan.baidu.com/s/…...

stable diffusion安装包和超火使用文档及提示词,数字人网址

一&#xff1a;文生图、图生图 1&#xff1a;stable diffusion&#xff1a;对喜欢二次元、美女小姐姐、大眼萌妹的人及其友好哈哈(o^^o) 1&#xff09;&#xff1a;关于安装包和模型包&#xff1a; 链接&#xff1a;https://pan.baidu.com/s/11_kguofh76gwhTBPUipepw 提取码…...

训练营:贪心篇

贪心就是&#xff1a;局部最优 1、455. 分发饼干 按照饼干分&#xff0c;从大到小&#xff0c;最大的给胃口最大能满足的 def findContentChildren455(g, s):g sorted(g,reverseTrue)s sorted(s,reverseTrue)j0c 0i0while(i<len(s) and j<len(g)):if s[i]>g[j]:c…...

四、Dubbo扩展点加载机制

四、Dubbo扩展点加载机制 4.1 加载机制概述 Dubbo良好的扩展性与框架中针对不同场景使用合适设计模式、加载机制密不可分 Dubbo几乎所有功能组件都是基于扩展机制&#xff08;SPI&#xff09;实现的 Dubbo SPI 没有直接使用 Java SPI&#xff0c;在它思想上进行改进&#xff…...

[保研/考研机试] KY103 2的幂次方 上海交通大学复试上机题 C++实现

题目链接&#xff1a; KY103 2的幂次方 https://www.nowcoder.com/share/jump/437195121691999575955 描述 Every positive number can be presented by the exponential form.For example, 137 2^7 2^3 2^0。 Lets present a^b by the form a(b).Then 137 is present…...

时序预测 | MATLAB实现基于BP神经网络的时间序列预测-递归预测未来(多指标评价)

时序预测 | MATLAB实现基于BP神经网络的时间序列预测-递归预测未来(多指标评价) 目录 时序预测 | MATLAB实现基于BP神经网络的时间序列预测-递归预测未来(多指标评价)预测结果基本介绍程序设计参考资料 预测结果 基本介绍 Matlab实现BP神经网络时间序列预测未来&#xff08;完整…...

组合模式(C++)

定义 将对象组合成树形结构以表示部分-整体’的层次结构。Composite使得用户对单个对象和组合对象的使用具有一致性(稳定)。 应用场景 在软件在某些情况下&#xff0c;客户代码过多地依赖于对象容器复杂的内部实现结构&#xff0c;对象容器内部实现结构(而非抽象接口)的变化…...

git上传问题记录

unable to access ‘https://github.com/songjiahao-wq/untitled.git/’: Failed to connect to github.com port 443 after 21086 ms: Couldn’t connect to serve 解决办法&#xff1a;修改 Git 的网络设置 打开git Bash运行&#xff0c;clash代理一般是下面的端口 # 注意…...

通过动态IP解决网络数据采集问题

动态地址的作用 说到Python网络爬虫&#xff0c;很多人都会遇到困难。最常见的就是爬取过程中IP地址被屏蔽。虽然大部分都是几个小时内自动解封的&#xff0c;但这对于分秒必争的python网络爬虫来说&#xff0c;是一个关键性的打击&#xff01;当一个爬虫被阻塞时&#xff0c;…...

可重入锁,不可重入锁,死锁的多种情况,以及产生的原因,如何解决,synchronized采用的锁策略(渣女圣经)自适应的底层,锁清除,锁粗化,CAS的部分应用

一、&#x1f49b; 锁策略——接上一篇 6.分为可重入锁&#xff0c;不可重入锁 如果一个线程&#xff0c;针对一把锁&#xff0c;连续加锁两次&#xff0c;会出现死锁&#xff0c;就是不可重入锁&#xff0c;不会出现死锁&#xff0c;就是可重入锁。 如果一个线程&#xff0c;针…...

【网络】每天掌握一个Linux命令 - iftop

在Linux系统中&#xff0c;iftop是网络管理的得力助手&#xff0c;能实时监控网络流量、连接情况等&#xff0c;帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...

ES6从入门到精通:前言

ES6简介 ES6&#xff08;ECMAScript 2015&#xff09;是JavaScript语言的重大更新&#xff0c;引入了许多新特性&#xff0c;包括语法糖、新数据类型、模块化支持等&#xff0c;显著提升了开发效率和代码可维护性。 核心知识点概览 变量声明 let 和 const 取代 var&#xf…...

突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合

强化学习&#xff08;Reinforcement Learning, RL&#xff09;是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程&#xff0c;然后使用强化学习的Actor-Critic机制&#xff08;中文译作“知行互动”机制&#xff09;&#xff0c;逐步迭代求解…...

安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件

在选煤厂、化工厂、钢铁厂等过程生产型企业&#xff0c;其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进&#xff0c;需提前预防假检、错检、漏检&#xff0c;推动智慧生产运维系统数据的流动和现场赋能应用。同时&#xff0c;…...

TRS收益互换:跨境资本流动的金融创新工具与系统化解决方案

一、TRS收益互换的本质与业务逻辑 &#xff08;一&#xff09;概念解析 TRS&#xff08;Total Return Swap&#xff09;收益互换是一种金融衍生工具&#xff0c;指交易双方约定在未来一定期限内&#xff0c;基于特定资产或指数的表现进行现金流交换的协议。其核心特征包括&am…...

自然语言处理——循环神经网络

自然语言处理——循环神经网络 循环神经网络应用到基于机器学习的自然语言处理任务序列到类别同步的序列到序列模式异步的序列到序列模式 参数学习和长程依赖问题基于门控的循环神经网络门控循环单元&#xff08;GRU&#xff09;长短期记忆神经网络&#xff08;LSTM&#xff09…...

select、poll、epoll 与 Reactor 模式

在高并发网络编程领域&#xff0c;高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表&#xff0c;以及基于它们实现的 Reactor 模式&#xff0c;为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。​ 一、I…...

selenium学习实战【Python爬虫】

selenium学习实战【Python爬虫】 文章目录 selenium学习实战【Python爬虫】一、声明二、学习目标三、安装依赖3.1 安装selenium库3.2 安装浏览器驱动3.2.1 查看Edge版本3.2.2 驱动安装 四、代码讲解4.1 配置浏览器4.2 加载更多4.3 寻找内容4.4 完整代码 五、报告文件爬取5.1 提…...

python执行测试用例,allure报乱码且未成功生成报告

allure执行测试用例时显示乱码&#xff1a;‘allure’ &#xfffd;&#xfffd;&#xfffd;&#xfffd;&#xfffd;ڲ&#xfffd;&#xfffd;&#xfffd;&#xfffd;ⲿ&#xfffd;&#xfffd;&#xfffd;Ҳ&#xfffd;&#xfffd;&#xfffd;ǿ&#xfffd;&am…...

处理vxe-table 表尾数据是单独一个接口,表格tableData数据更新后,需要点击两下,表尾才是正确的

修改bug思路&#xff1a; 分别把 tabledata 和 表尾相关数据 console.log() 发现 更新数据先后顺序不对 settimeout延迟查询表格接口 ——测试可行 升级↑&#xff1a;async await 等接口返回后再开始下一个接口查询 ________________________________________________________…...