位置:首页 » 技术 » 最长公共子字符串算法 JAVA兑现

最长公共子字符串算法 JAVA兑现

日期:2013-10-31 阅读:0num
Advertisement

最长公共子字符串算法 JAVA实现
什么是最长公共子字符串算法? 举一个例子就清楚了
比如我们有两个字符串:
Please, peter go swimming!
I’m peter goliswi
那么该算法应该输出’peter go’. 最长公共子字符串算法通过suffix trees算法 (时间复杂度O(n),但是实现极其复杂) 可以获得效率很高的实现。但是在本帖中我们要使用效率稍次的‘动态编程’思想来实现该算法。动态编程,顾名思义, 就是重用前一步已经计算出来的信息。要理解这种实现,我们首先需要填写一个二维的整数型数组,假如我们用i表示水平方向的字符串(Please, peter go swimming!),以j表示垂直方向的字符串(I’m peter goliswi) 如图:

please, peter go swimming
i 0000000000000000000100100
' 0000000000000000000000000
m 0000000000000000000011000
  0000000100000100100000000
p 1000000020000000000000000
e 0010010003000000000000000
t 0000000000400000000000000
e 0010010001050000000000000
r 0000000000006000000000000
  0000000100000700100000000
g 0000000000000080000000000
o 0000000000000009000000000
l 0100000000000000000000000
i 0000000000000000000100100
s 0001000000000000010000000
w 0000000000000000002000000
i 0000000000000000000300100

当i=19 j=0时我们得到第一个相等的字符‘i’,这时把相应的index对应的数组值设为1;
依此类推继续填表;
当 i= 8 j= 4时我们得到另一个相等的字符’ ’(空格),现在我们要重用前一步的计算结果(num[7][3]=1)
所以num[8][4] = 1 + num[7][3]就应该是2.这样我们就得到了一个长度为2的相等子字符串;
以此规则填完这个动态表;

下面是一段参考实现

public static String longestSubstring(String str1, String str2) {

StringBuilder sb = new StringBuilder();
if (str1 == null || str1.isEmpty() || str2 == null || str2.isEmpty())
  return "";

// ignore case
str1 = str1.toLowerCase();
str2 = str2.toLowerCase();

// java initializes them already with 0
int[][] num = new int[str1.length()][str2.length()];
int maxlen = 0;
int lastSubsBegin = 0;

for (int i = 0; i < str1.length(); i++) {
for (int j = 0; j < str2.length(); j++) {
  if (str1.charAt(i) == str2.charAt(j)) {
    if ((i == 0) || (j == 0))
       num[i][j] = 1;
    else
       num[i][j] = 1 + num[i - 1][j - 1];

    if (num[i][j] > maxlen) {
      maxlen = num[i][j];
      // generate substring from str1 => i
      int thisSubsBegin = i - num[i][j] + 1;
      if (lastSubsBegin == thisSubsBegin) {
         //if the current LCS is the same as the last time this block ran
         sb.append(str1.charAt(i));
      } else {
         //this block resets the string builder if a different LCS is found
         lastSubsBegin = thisSubsBegin;
         sb = new StringBuilder();
         sb.append(str1.substring(lastSubsBegin, i + 1));
      }
   }
}
}}

return sb.toString();
}
相关文章
  • 最长公共子字符串算法 JAVA兑现

    最长公共子字符串算法 JAVA实现 什么是最长公共子字符串算法? 举一个例子就清楚了 比如我们有两个字符串: Please, peter go swimming! I'm peter goliswi 那么该算法应该输出'peter go'. 最长公共子字符串算法通过suffix trees算法 (时间复杂度O(n),但是实现极其复杂) 可以获得效率很高的实现.但是在本帖中我们要使用效率稍次的'动态编程'思想来实现该算法.动态编程,顾名思义, 就是重用前一步已经计算出来的信息.要理解这种实现,我们

  • Java动态规划 兑现最长公共子序列以及最长公共子字符串 Java动态规划 兑现最长公共子序列以及最长公共子字符串

    Java动态规划 实现最长公共子序列以及最长公共子字符串 动态规划法 经常会遇到复杂问题不能简单地分解成几个子问题,而会分解出一系列的子问题.简单地采用把大问题分解成子问题,并综合子问题的解导出大问题的解的方法,问题求解耗时会按问题规模呈幂级数增加. 为了节约重复求相同子问题的时间,引入一个数组,不管它们是否对最终解有用,把所有子问题的解存于该数组中,这就是动态规划法所采用的基本方法. [问题] 求两字符序列的最长公共字符子序列 问题描述:字符序列的子序列是指从给定字符序列中随意地(不一定连续)

  • 使用后缀数组找寻最长公共子字符串JavaScript版 使用后缀数组找寻最长公共子字符串JavaScript版

    使用后缀数组寻找最长公共子字符串JavaScript版 后缀数组很久很久以前就出现了,具体的概念读者自行搜索,小菜仅略知一二,不便讨论. 本文通过寻找两个字符串的最长公共子字符串,演示了后缀数组的经典应用. 首先需要说明,小菜实现的这个后缀数组算法,并非标准,只是借鉴了其中的思想. 小菜实现的算法,有两个版本,第一个是空间换时间,第二个是时间换空间. 空间换时间版本 1 /* 2 利用后缀数组获取两个字符串最长公共子字符串 3 空间换时间版本 4 @params 5 s1 String,要分析的

  • 最长公共子字符串

    描述: 求两个输入序列的最长的公共子字符串的长度.子字符串中的所有字符在源字符串中必须相邻. 如字符串:21232523311324和字符串312123223445,他们的最长公共子字符串为21232,长度为5. 输入格式: 两行,第一行为第一个字符串X,第二行为第二个字符串Y,字符串不含空格并以回车标示结束.X和Y的串长都不超过100000. 输出格式: 两行,第一行为最长的公共子字符串的长度,第二行输出一个最长的公共子字符串. 说明: (1)若最长的公共子字符串有多个,请输出在源字符串X中靠

  • 算法导论-LCS有关问题(最长公共子系列) 算法导论-LCS有关问题(最长公共子系列)

    算法导论--------------LCS问题(最长公共子系列) 1.基本概念 一个给定序列的子序列就是该给定序列中去掉零个或者多个元素的序列.形式化来讲就是:给定一个序列X={x1,x2,--,xm},另外一个序列Z={z1.z2.--,zk},如果存在X的一个严格递增小标序列<i1,i2--,ik>,使得对所有j=1,2,--k,有xij = zj,则Z是X的子序列.例如:Z={B,C,D,B}是X={A,B,C,B,D,A,B}的一个子序列,相应的小标为<2,3,5,7>.从

  • 最长公共子序列-【算法导论】 最长公共子序列-【算法导论】

    最长公共子序列--[算法导论] 最长公共子序列:一个序列 S ,如果分别是两个或多个已知序列的子序列,且是所有符合此条件序列中最长的,则 S 称为已知序列的最长公共子序列: 其核心很简单: 这样,构造子结构就比较简单了: if(str1[i - 1] == str2[j - 1]) m[i][j] = m[i - 1][j - 1] + 1; else m[i][j] = max(m[i - 1][j], m[i][j - 1]); 前面动态规划思想说得足够了,这次直接贴: #include <

  • Uva 10635 - Prince and Princess(最长公共子序列 nlogn 算法)

    题目大意: 一个n*n的棋盘(2 <= n <= 250),一个p+1个数的数组,各个数互不相同,第一个数是1,最后 一个数是n*n:一个q+1个数的数组,各个数互不相同,第一个数是1,最后 一个数是n*n:1 <= p,q < n*n:问这两个数组的LCS. 题目分析: 这个题目显然用n^2的最长公共子序列的算法会超时,看<信息竞赛入门经典>的解析,原来最长公共子序列可以转化成最长上升子序列的问题,然后用最长上升子序列的 nlogn 的算法求解. 可以在google或

  • 【字符串处理算法】获取最长公共子串的算法设计及C代码实现过程分析

    一.需求描述 输入两个字符串,编写程序获取这两个字符串的第一个最长公共子串. 例如,输入的字符串为"abcdef"和"fecdba",那么这两个字符串的第一个最长公共子串为"cd". 二.算法设计 我们可以首先寻找两个字符串中的第一个相等的字符,然后分别向后移动来比较对应位置的字符是否相等. 即如果字符串1为"1234abcd",字符串2为"abd",那么首先发现字符串1中的第五个字符"a&quo

  • 聚类算法之单链接算法java兑现

    聚类算法之单链接算法java实现 聚类算法中基于链接的算法大致有三种:单链接算法(single link),平均链接算法(average link),最小生成数算法(minimum spanning tree).现在实现单链接算法,其他算法以后再续吧. 单链接算法的过程是 首先生成各个元素的距离矩阵,根据距离和阀值的比对来控制生成的聚类个数,阀值越大,生成的聚类越少,直到同属一类. 下面例子实现了根据经纬度来实现城市的聚类. package test.algorithm; import java

  • RSA算法Java兑现 RSA算法Java兑现

    RSA算法Java实现 Java代码 package com.hexun.blog.dongliwei.utils; import javax.crypto.Cipher; import java.security.*; import java.security.spec.RSAPublicKeySpec; import java.security.spec.RSAPrivateKeySpec; import java.security.spec.InvalidKeySpecException;

  • 五子棋AI算法 Java兑现

    五子棋AI算法 Java实现 五子棋AI算法 也算是一个典型的游戏AI算法,一些棋类的AI算法都可以参考实现,下面是Java实现代码 棋盘抽象接口 import java.util.List; public interface IChessboard { //取得棋盘最大横坐标 public int getMaxX(); //最大纵坐标 public int getMaxY(); //取得当前所有空白点,这些点才可以下棋 public List<Point> getFreePoints();

  • AES算法Java兑现(转)

    AES算法Java实现(转) package com.tristan.aes; import java.io.UnsupportedEncodingException; import java.security.InvalidKeyException; import java.security.NoSuchAlgorithmException; import java.security.SecureRandom; import javax.crypto.BadPaddingException;

  • 表达式算法java兑现

    表达式算法java实现 package bd; import java.util.Scanner; import java.util.Stack; public class Calculator { public static final String USAGE = "== usage ==\n" + "input the expressions, and then the program " + "will calculate them and sho

  • TFIDF算法java兑现 TFIDF算法java兑现

    TFIDF算法java实现 转载自: http://xwrwc.blog.163.com/blog/static/46320003201010634132451/ 一.算法简介 TF-IDF(term frequency–inverse document frequency). TFIDF的主要思想是:如果某个词或短语在一篇文章中出现的频率TF高,并且在其他文章中很少出现,则认为此词或者短语具有很好的类别区分能力,适合用来分类.TFIDF实际上是:TF*IDF,TF词频(Term Frequen

  • CRC16算法Java兑现

    CRC16算法Java实现 模仿C++代码改写的Java实现 public class CRC16 { private short[] crcTable = new short[256]; private int gPloy = 0x1021; // 生成多项式 public CRC16() { computeCrcTable(); } private short getCrcOfByte(int aByte) { int value = aByte << 8; for (int count

  • 各种排序算法Java兑现 各种排序算法Java兑现

    各种排序算法Java实现 校招快要开始了,复习一下以前的排序知识,下面的代码都是以前写的,今天翻出来又重新看了一下,贴上来.也算是复习吧. 插入排序,稳定排序(稳定是指相同的两个数在排序之后它们的相对位置不变.): //插入排序 public static void insertSort(int[] a){ int len = a.length; //遍历数组 for(int i=1;i<len;i++){ int temp = a[i]; int j=i-1; while(j>=0&

  • 各种排序算法 java兑现

    各种排序算法 java实现 package org.rut.util.algorithm.support; import org.rut.util.algorithm.SortUtil; /** * @author treeroot * @since 2006-2-2 * @version 1.0 */ public class InsertSort implements SortUtil.Sort{ /* (non-Javadoc) * @see org.rut.util.algorithm.

  • Dijkstra算法java兑现

    Dijkstra算法java实现 Dijkstra算法是典型最短路算法,用于计算一个节点到其他所有节点的最短路径.主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止.Dijkstra算法能得出最短路径的最优解,但由于它遍历计算的节点很多,所以效率低. Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法,用于计算一个节点到其他所有节点的最短路径.主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止.Dijkstra算法是很有代表性的最短路径算法,在很多专业课程中都作为基本内容有详

  • PageRank算法java兑现版本

    PageRank算法java实现版本 PageRank算法是Google的核心搜索算法,在所有链接型文档搜索中有极大用处,而且在我们的各种关联系统中都有好的用法,比如专家评分系统,微博搜索/排名,SNS系统等. PageRank算法的依据或思想: 1,被重要的网页链接的越多(外链) ,此网页就越重要 2,此网页对外的链接越少越重要 这两个依据不能是独立的,是需要一起考虑的.但是问题来了,我们怎样判断本网页的外链是很重要的呢?循环判断?那不死循环了? 解决办法是:给定阀值,让循环在此临界处停止.

  • 动态规划算法解最长公共子序列LCS问题 动态规划算法解最长公共子序列LCS问题

    第一部分.什么是动态规划算法 ok,咱们先来了解下什么是动态规划算法. 动态规划一般也只能应用于有最优子结构的问题.最优子结构的意思是局部最优解能决定全局最优解(对有些问题这个要求并不能完全满足,故有时需要引入一定的近似).简单地说,问题能够分解成子问题来解决. 动态规划算法分以下4个步骤: 描述最优解的结构递归定义最优解的值按自底向上的方式计算最优解的值 //此3步构成动态规划解的基础.由计算出的结果构造一个最优解. //此步如果只要求计算最优解的值时,可省略. 好,接下来,咱们讨论适合采用动

最新文章
  • [稀土掘金日报] 给设计师推荐的资源合集 [稀土掘金日报] 给设计师推荐的资源合集

    本期日报稀土君为大家准备了一箩筐资源,包含了基于行为科学的产品设计方法,移动端设计的提示,还有各种 UI / UX 图片设计资源合集,设计师绝对不能错过哦. 第一篇文章来自掘金翻译计划,欢迎加入我们翻译更多优秀的技术文章,随手点个 star 也是极好的. [译] Animated SVG vs GIF 掘金翻译计划: SVG 不仅可用于展示静态图像,与其它图片格式相比,呈现动画的能力只是其强大的特性之一.这也是 SVG 优于包括 GIF 在内的其它位图格式的众多原因之一. 百度 MUX: 基于行

  • 大家用 Axure 做一套原型图需要多久?

    第一次用 Axure ,我花了一天半才做了四个网站页面的原型图,这中间的过程有思考网站设计,有对比参考花的时间,有学习 Axure 怎么用. 想知道真正在干产品经理的同学做一套网站的原型图大概要多久? --cut-- squall7902在2016-05-09 17:56:32回答到: 这个肯定看你做多少东西来定. charzluo在2016-05-09 17:56:32回答到: 看你细到什么程度了,如果各种弹窗,各种动态面板,确实很费时间,但是如果只是展示逻辑和部分交互时间还好. 所以一般我都

  • 教师辞职信范文

    尊敬的校长: 你好. 首先向你说声对不起,我辜负了你对我的期望,今天写信是向您提出辞职的. 自去年分配到我校以来,我一直受到了您的各方面的帮助,对此我是感恩不尽的.刚大学毕业,我由一名学生成了一位光荣的人民教师,对教师这职业我是既熟悉又陌生.感谢一年来您和诸位校领导对我的悉心栽培和备至关怀.来Xx小学已经有一年了,当初刚来学校时我什么也不懂,胆子也很小.正是在您的帮助下,我才适应了环境,了解了学校的基本情况,使得自己的工作走上了正轨. 回忆总是甜蜜的.在Xx小学的时候,我总会去看看学校那口古老的

  • 荆轲刺秦王阅读练习及答案

    荆轲刺秦王(节选) 荆轲奉樊於期头函,而秦武阳奉地图匣,以次进.至陛下,秦武阳色变振恐,群臣怪之,荆轲顾笑武阳,前为谢曰:"北蛮夷之鄙人,未尝见天子,故振慑,愿大王少假借之, 使毕使于前."秦王谓轲曰:"起,取武阳所持图!" 轲既取图奉之,发图,图穷而匕首见.因左手把秦王之袖,而右手持匕首揕之.未至身,秦王惊,自引而起,绝袖.拔剑,剑长,操其室.时恐急,剑坚,故不可立拔. 荆轲逐秦王,秦王还柱而走.群臣惊愕,卒起不意,尽失其度.而秦法,群臣侍殿上者,不得持尺兵:诸郎

  • PhotoShop中涂鸦类插画上色技法教程 PhotoShop中涂鸦类插画上色技法教程

    一群热爱插画并长期从事插画的朋友有缘一起制作<爱绘生活>,这本书主要通过二十多位插画师不同的工作经历与近期作品,插画技法交流,以及推荐喜欢绘本书和网站让喜欢插画的朋友离插画更进一步,一起感受插画带给我们的快乐. 此书正在制作过程,很多方面还需要不断完善.目前在网上会发书的部分,欢迎广大网友多提宝贵意见,有您的观注和帮助我们竭力做得更好! (所有插画版权所有,仅供技术交流,严禁任何形式的非法商用) 说明一下这个教程是最简单最便于入手的上色方法,希望能对刚刚开始学插画的朋友能有所帮助.插画的风格和

  • 《责任胜于能力》读后感

    一位伟人曾说过:"人生所有的履历都必须排在勇于负责的精神之后."在责任的内在力量的驱使下,我们常常油然而生一种崇高的使命感和归属感.一个企业管理者说:"如果你能真正钉好一枚纽扣,这应该比你缝制出一件粗制滥造的衣服更有价值."尽职尽责地对待自己的工作,无论自己的工作是什么,重要的是你是否真正做好了你的工作. "学会感恩是担当责任的基础,成功不是一种机会,而是一种选择!学会感恩,选择责任!"这段文字出自<责任胜于能力>一书.在对书中章节一

  • 有关关心朋友的短信

    有关关心朋友的短信,经常幻想一个场景:我妈像电视剧里一样酷酷的掏出十几万甩给我女朋友说"钱给你,离开他,不准再联系他了"我一定会冲上去把钱都抢回来说:"妈,为什么要便宜外人?我绝对不会再联系她了!这些钱给我啊!" 1.衣不过暖,食不过饱:住不过奢,行不过富:喜不过欢,利不过贪:劳不过累,逸不过安:友不过忘,联系为佳:保重身体,祝你平安! 2.奥运期间,球赛火爆,问候给你一个"球"!愿你事业像篮球,越拍越高:烦恼像足球,一脚踢开:心情像乒乓球,蹦蹦

  • vst全聚合安装到天猫盒子的图文教程 vst全聚合安装到天猫盒子的图文教程

    vst全聚合怎么装到天猫盒子呢,这个vst全聚合是非常的好用并且实用了,但许多的朋友不太会玩了,下面我来告诉各位这个怎么玩吧,希望文章能够对各位带来帮助. 我们先要在电脑端下载VST全聚合客户端,下载完毕拷贝至U盘. 用U盘接至天猫魔盒USB接口,桌面将自动跳出发现外接存储设备提示,如下图. 此时点击全部,打开U盘,找到你下载好的APK文件,单击开始安装. 安装完成后,退出文件管理器,去应用里看看,是不是已经有了VST全聚合,单击打开,如下图分类较多,直播,点播,应用管理,以及自启动设置都有.

  • 缓缓的学。细细的用

    慢慢的学.细细的用. 刚注册的JAVAEYE 居然要等一天才能写BLOG.终于熬过一天.开博写文字.第一篇方向. 永远只做对的事.坚持,努力.

  • PDF解析记要&mdash;&mdash;Pdfbox PDF解析记要&mdash;&mdash;Pdfbox

    PDF解析记录--Pdfbox 此文仅作记录[嫌放电脑里碍事-_-],内容为以前收集的一小段代码. 下面为pdf获取文本的简要代码片段: private string GetPDFText(string filename) { PDDocument pdf = PDDocument.load(filename); PDFTextStripper pdftext = new PDFTextStripper(); return pdftext.getText(pdf); } 其中对于旧版本,如pdf

热门推荐
  • iphone6港版支持移动4g吗? iphone6港版支持移动4g吗? iphone6港版支持移动4g吗?有很多果粉问iphone6港版移动4g能不能用.因为国内并不是首发国家,所以很多机友就考虑入手港版,那么港版能不能使用移动4G呢?让我们通过下文了解吧. 从苹果香港官网提供的数据来看,港版iPhone 6共有A1549和A1586两个型号.其中A1549又分为GSM版和CDMA版,GSM版支持GSM/EDGE/WCDMA/FDD-LTE制式,而CDMA版则支持GSM/EDGE/CDMA EV-DO/WCMDA/LTE FDD制式. 而A1586则和国行版的网络制
  • 英伟达将与IBM联合推出超级计算机 英伟达将与IBM联合推出超级计算机 据国外媒体报道,英伟达周一宣布与IBM就联合推出超级计算机达成合作意向.前者在双方合作中将负责提供Telsa系列GPU加速处理器,后者则负责提供Power处理器及整机系统.此次合作标志着GPU加速处理技术首次成为企业数据中心超级计算机应用的核心技术. "企业如今正寻找新的且更加有效的方式来从大数据的分析中推动企业价值."IBM系统技术部门及集成供应链高级副总裁汤姆·罗萨米利亚(Tom Rosamilia)表示,"IBM与英伟达的组合能够为客户提供这样一个高级.高效的基石,以实
  • OA办公系统是什么意思? OA办公系统是什么意思? OA办公系统其实就是办公自动化系统,它是用网络和OA软件一起建立的一个单位内部的办公通信平台,它的用处是用来辅助办公的.可以通过OA系统来完成单位内部的邮件通信.信息发布.文档管理.工作流程自动化等等. oa办公系统时采用Internet技术,然后使企业内部人员能快速便捷的共享信息,高效地协同工作,相比起来比过去的手工办公方式更能实现迅速.全方面的信息采集.信息处理.让企业的管理更方便.办公自动化可以和一个企业的业务结合的非常紧密,甚至是定制的.因而可以将诸如信息采集.查询.统计等功能与具体业务
  • 三个步骤解决win7系统本地组策略打不开的问题 三个步骤解决win7系统本地组策略打不开的问题 第一步.首先单击开始菜单或者是直接单击键盘上的windows图标,这样就可以打开电脑的快捷菜单了. 第二步.在打开的快捷菜单窗口中,点击右下角的运行选项,也可以直接同时按下键盘上的win+r快捷键打开运行窗口; 第三步.在运行窗口中,输入regedit并单击回车,就可以打开注册表编辑器窗口了,在注册表编辑器窗口的左侧菜单中依次点击展开" HKEY_CURRENT_USERSoftwarePoliciesMicrosoftMmc{8FC0B734-A0E1-11D1-A7D3- 0000F8757
  • 7 MapX