淘宝网站怎么做的好看,创新的南昌网站建设,wordpress 优惠券 插件,网页生成app计算两个字符串之间的重复率 最长公共子序列实现代码 最长公共子序列
基于最长公共子序列#xff08;Longest Common Subsequence, LCS#xff09;的重复率的中心逻辑是首先找到两个或多个序列中同时出现的、不一定连续但保持相对顺序的最长子序列#xff0c;然后计算这个最… 计算两个字符串之间的重复率 最长公共子序列实现代码 最长公共子序列
基于最长公共子序列Longest Common Subsequence, LCS的重复率的中心逻辑是首先找到两个或多个序列中同时出现的、不一定连续但保持相对顺序的最长子序列然后计算这个最长公共子序列的长度与两个或多个序列中较长字符串长度的比值通常以百分比的形式表示。 重复率 (LCS的长度 / 较长字符串的长度) * 100% 这种基于最长公共子序列的重复率计算方法常用于衡量两个字符串的相似性或重复程度特别是在文本比较、DNA序列分析、版本控制等领域。然而需要注意的是这种方法只能捕捉到字符串中的顺序相似性而不能捕捉到非顺序的相似性如字符频率或编辑距离。
实现代码
import java.util.HashSet;
import java.util.Set;
import java.util.HashMap;
import java.util.Map;public class Main {// 使用动态规划计算最长公共子序列的长度public static int longestCommonSubsequenceLength(String strA, String strB) {int m strA.length();int n strB.length();int[][] dp new int[m 1][n 1];for (int i 1; i m; i) {for (int j 1; j n; j) {if (strA.charAt(i - 1) strB.charAt(j - 1)) {dp[i][j] dp[i - 1][j - 1] 1;} else {dp[i][j] Math.max(dp[i - 1][j], dp[i][j - 1]);}}}return dp[m][n];}// 计算重复率public static double calculateDuplicationRateBasedOnLCS(String strA, String strB) {int lcsLength longestCommonSubsequenceLength(strA, strB);int shorterLength Math.min(strA.length(), strB.length());return (double) lcsLength / shorterLength * 100;}public static void main(String[] args) {String strA 这两天河北廊坊市人民医院退还核酸检测费的消息引发热议。奔流新闻记者从廊坊市人民医院财务科证实“从5月20日开始对收到短信的市民退费多数成年人已经完成退费今天开始对青少年儿童退费。”;String strB 5月20日一些市民收到廊坊市人民医院发来的短信按上级要求退还2020年至2021年核酸检测费。请持身份证于5月20日-6月20日工作日时间到市医院财务部退费。;double rate calculateDuplicationRateBasedOnLCS(strA, strB);System.out.println(基于最长公共子序列的重复率: rate %);}}
执行结果
