欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2024-03-08 14:32:46
背景 对算法一直应用的比较少,最近看到一些典型的算法想练练手,想看看到底有多么让人讨厌。其实发现算法都有一定的套路,一般并不是临时凭空想出来的,大都建立在一些已经存在的经...

背景

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

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