计算两个字符串最大公有子串

背景

对算法一直应用的比较少，最近看到一些典型的算法想练练手，想看看到底有多么让人讨厌。其实发现算法都有一定的套路，一般并不是临时凭空想出来的，大都建立在一些已经存在的经典算法知识以及数据结构上。换句话来说，如果某些玩法之前未接触过，那么让你在短时间内临时想出来还是有一定难度的。这有点类似项目经验，如果曾经做过一个CRM系统，下次再碰到它时你就轻松很多，如果你挑战的是一个你从未遇到过的系统，你只能凭已有知识去强吃。

计算两个字符串最大公共子串

这个也是经常遇到到，给出两个任意长度的字符串，输出最大公有字符串，比如输入abcdef，cdef，则输出cdef。

解决方案

采用双层循环，指针移动来记录所有子串，最后取最大长度子串。利用临时队列来存储循环过程中匹配成功的字符元素，从两个字符串首个元素开始匹配。

  • 如果a.charAt(i)=b.charAt(j)，标记开始匹配，同时移动两者指针，并将相同字符串压入临时队列中
  • 如果a.charAt(i)!=b.charAt(j)，只移动b的指针。如果处于匹配中，则将临时队列存储到结果集中，并清空临时队列。
  • 如果a,b任意一个到了最后一个元素，将临时队列中的值存储到结果集中，并清空临时队列

示意图

从元素0开始比较

字符串A指针不动，B依次向后找至少找到相同的，将相同字符压入临时队列中。

出现第一个匹配元素

当出现匹配元素后，两个字符串均向后移动一个元素再做比较。

匹配出现中断

如果前面已经开始匹配成功，向后出现字符不相同时，终止。

重置索引，循环匹配

字符串B指针向后移动，字符串A的指针重置，递归上面的步骤。

示例代码

下面的示例将所有子串均记录下来，如果只想输出最大子串需要改下逻辑，定义一个最大子串，然后与循环计算的子串相比较，取两者长度最大值即可。

String b="abcdeqwe";
String a="cdeabrwqedeqwe";
int lengthA=a.length();
int lengthB=b.length();
//标识是否开始匹配
boolean match=false;
//循环中用于存储相同字符的临时队列
Queue tmpResult=new ArrayQueue();
//存储所有子串
List<Queue> result=new ArrayList<>();
for(int i=0;i<lengthA;i++){
 int indexA=i;
 for(int j=0;j<lengthB;j++){
  if(a.charAt(indexA)==b.charAt(j)){
   if(!match) {
    match = true;
   }
   tmpResult.add(a.charAt(indexA));
   if(indexA<lengthA-1) {
    indexA++;
   }
  }
  else {
   if(match) {
    result.add(tmpResult);
    //重置条件
    tmpResult=new ArrayQueue();
    indexA=i;
   }
  }
  if(j==lengthB-1||i==lengthA-1){
   if(!tmpResult.isEmpty()){
    result.add(tmpResult);
    //重置条件
    tmpResult=new ArrayQueue();
   }
  }
 }
}
//取最大的子串
Queue stringResult= Collections.max(result, new Ordering<Queue>() {
 @Override
 public int compare(Queue left, Queue right) {
  return Integer.compare(left.size(),right.size());
 }
});

优点

指针移动在循环过程中不会产生多余的临时字符串，如果是substring方案就需要考虑效率了。

以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，同时也希望多多支持我们！

赞 (0)

相关推荐

  • JavaScript实现计算字符串中出现次数最多的字符和出现的次数

    "计算出字符串中出现次数最多的字符是什么,出现了多少次?" 看到这个需求,我想大多数人应该首先想到的是转换成数组,再做处理,当然是可以解决问题的,然后这里提供一个巧妙的算法设计,无需转数组,可以很快解决问题,代码如下: 复制代码 代码如下: var str = "adadfdfseffserfefsefseeffffftsdg"; var maxLength = 0; var result = ""; while(str!=''){     ol

  • C#和SQL实现的字符串相似度计算代码分享

    C#实现: 复制代码 代码如下: #region 计算字符串相似度         /// <summary>         /// 计算字符串相似度         /// </summary>         /// <param name="str1">字符串1</param>         /// <param name="str2">字符串2</param>         ///

  • Lua判断字符串中包含中文字符的方法和计算字符串宽度函数分享

    一.判断字符串中包含中文字符的方法 遍历数组,对每个字节使用string.byte(),发现有大于127的,就是汉字,可以参照下面的代码. 二.计算字符串宽度函数 复制代码 代码如下: -- 计算字符串宽度   local str = "Jimmy: 你好,世界!" local fontSize = 20 local lenInByte = #str local width = 0   for i=1,lenInByte do     local curByte = string.by

  • JavaScript indexOf方法入门实例（计算指定字符在字符串中首次出现的位置）

    JavaScript indexOf 方法 indexOf 方法用于计算某个指定的字符串在字符串中首次出现的位置,并返回该数值.其语法如下: 复制代码 代码如下: str_object.indexOf( search, start ) 参数说明: 参数 说明 str_object 要操作的字符串(对象) search 必需.要检索的字符串 start 可选.指定开始检索的位置,如省略该参数,则将从字符串的首字符开始检索 提示:字符串是从 0 开始计数的. indexOf 方法实例 复制代码 代码

  • PHP改进计算字符串相似度的函数similar_text()、levenshtein()

    similar_text()中文汉字版 复制代码 代码如下: <?php       //拆分字符串       function split_str($str) {         preg_match_all("/./u", $str, $arr);         return $arr[0];       }              //相似度检测       function similar_text_cn($str1, $str2) {         $arr_1

  • C语言中计算字符串长度与分割字符串的方法

    C语言strlen()函数:返回字符串的长度 头文件: #include <string.h> strlen()函数用来计算字符串的长度,其原型为: unsigned int strlen (char *s); [参数说明]s为指定的字符串. strlen()用来计算指定的字符串s 的长度,不包括结束字符"\0". [返回值]返回字符串s 的字符数. 注意一下字符数组,例如 char str[100] = "http://see.xidian.edu.cn/cpp

  • C#计算字符串哈希值（MD5、SHA）的方法小结

    C#计算字符串哈希值（MD5、SHA）的方法小结

    本文实例讲述了C#计算字符串哈希值(MD5.SHA)的方法.分享给大家供大家参考.具体如下: 一.关于本文 本文中是一个类库,包括下面几个函数: ① 计算32位MD5码(大小写):Hash_MD5_32 ② 计算16位MD5码(大小写):Hash_MD5_16 ③ 计算32位2重MD5码(大小写):Hash_2_MD5_32 ④ 计算16位2重MD5码(大小写):Hash_2_MD5_16 ⑤ 计算SHA-1码(大小写):Hash_SHA_1 ⑥ 计算SHA-256码(大小写):Hash_SHA

  • 利用PHP函数计算中英文字符串长度的方法

    本文实例讲述了利用PHP函数计算中英文字符串长度的方法.分享给大家供大家参考.具体实现方法如下: 一般来说大家知道英文字符占一个字节,而中文字符gbk占两个字符,utf8占三个字符,很多人印象中php计算字符串长度就是strlen()函数,其实不然,它计算的是字节的长度而非字符的长度,那么如何获取一个字符串中字符的长度呢?还有有mb_strlen(). 具体代码如下: 复制代码 代码如下: echo $str = 'PHP点点通'; echo strlen($str); //3*1+3*3=12

  • Shell脚本计算字符串长度和判断字符串为空小技巧

    一些需要注意的脚本问题 计算字符串长度可用的三种方法: 复制代码 代码如下: echo "$str"|awk '{print length($0)}' expr length "$str" echo "$str"|wc -c 但是第三种得出的值会多1,可能是把结束符也计算在内了 判断字符串为空的方法有三种: 复制代码 代码如下: if [ "$str" =  "" ] if [ x"$str&qu

  • Lua中计算、执行字符串中Lua代码的方法

    Lua中计算、执行字符串中Lua代码的方法

    一.Lua中执行字符串 运行过程中有个问题,我有个字符串,是一个数学表达式,如何计算这个字符串表达式的值呢? 比如,local param = "7*100", 我需要的结果其实是700,但是怎么样直接计算出这个值呢?方法如下 字符串前面 加个 "return" 然后loadstring以后得到一个function 然后执行获得700的返回值,这样通过转化,得到的结果如下: 二.以字符串形式执行Lua代码 有时候,我们在代码中希望能够动态的切换上下文,改变程序的处理

随机推荐