计算两个字符串最大公有子串_网络技术_宿州市腾雀网络科技有限公司

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

发布时间 - 2026-01-10 22:45:23 点击率：次

背景

对算法一直应用的比较少，最近看到一些典型的算法想练练手，想看看到底有多么让人讨厌。其实发现算法都有一定的套路，一般并不是临时凭空想出来的，大都建立在一些已经存在的经典算法知识以及数据结构上。换句话来说，如果某些玩法之前未接触过，那么让你在短时间内临时想出来还是有一定难度的。这有点类似项目经验，如果曾经做过一个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方案就需要考虑效率了。

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

# 计算 # 字符串 # C语言中计算字符串长度与分割字符串的方法 # C#计算字符串哈希值（MD5、SHA）的方法小结 # Lua中计算、执行字符串中Lua代码的方法 # Shell脚本计算字符串长度和判断字符串为空小技巧 # Lua判断字符串中包含中文字符的方法和计算字符串宽度函数分享 # JavaScript实现计算字符串中出现次数最多的字符和出现的次数 # 利用PHP函数计算中英文字符串长度的方法 # PHP改进计算字符串相似度的函数similar_text()、levenshtein() # JavaScript indexOf方法入门实例（计算指定字符在字符串中首次出现的位置） # C#和SQL实现的字符串相似度计算代码分享 # 有一定 # 想出 # 递归 # 清空 # 过程中 # 的是 # 如果你 # 让人 # 第一个 # 你就 # 已有 # 时间内 # 数据结构 # 不动 # 并将 # 做过 # 只想 # 已经开始 # 想看 # 句话

相关栏目：【网站优化151355 】【网络推广146373 】【网络技术251813 】【 AI营销90571 】

上一篇：如何使用SSH命令将网站文件上传到服务器？

下一篇：Laravel开发：如何使用Laravel Cashier实

相关栏目网站优化
网络推广
网络技术
AI营销

最新文章 Sublime怎么一键压缩JS代码 Su sublime如何在搜索中使用正则表达式 Sublime如何设置透明窗口效果 Su mysql如何设计商品表结构_mysql css属性背景图不显示怎么办_通过检查路如何使用Golang实现排序_Golan 农历闰月是怎么回事_为合回归年加一月调整塑造《刺客信条》艾吉奥传奇的编剧离开育碧 1英里等于多少公里 1mile和km的换 css grid布局中行和列是如何定义的 PS批量旋转和翻转图片，快速校正图片方向 C# Swagger UI自定义方法 C OPPO手机九宫格和全键盘怎么切换_OP Go语言如何实现用户登录注册_Golan 1节飞行速度多少公里每小时 1节是多少公纸嫁衣8千子树第五章庙门怎么开启庙门 Laravel 多行数据编辑表单中实现逐明日之后如何提升钓鱼等级明日之后提升钓支付宝怎样查年度账单_支付宝年度账单查看 C# 多线程UI更新Dispatcher

上一篇：如何使用SSH命令将网站文件上传到服务器？

下一篇：Laravel开发：如何使用Laravel Cashier实