最新下载
热门教程
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
计算两个字符串最大公有子串
时间:2017-03-03 编辑:简简单单 来源:一聚教程网
背景
对算法一直应用的比较少,最近看到一些典型的算法想练练手,想看看到底有多么让人讨厌。其实发现算法都有一定的套路,一般并不是临时凭空想出来的,大都建立在一些已经存在的经典算法知识以及数据结构上。换句话来说,如果某些玩法之前未接触过,那么让你在短时间内临时想出来还是有一定难度的。这有点类似项目经验,如果曾经做过一个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"; intlengthA=a.length(); intlengthB=b.length(); //标识是否开始匹配 booleanmatch=false; //循环中用于存储相同字符的临时队列 Queue tmpResult=newArrayQueue(); //存储所有子串 List for(inti=0;i intindexA=i; for(intj=0;j if(a.charAt(indexA)==b.charAt(j)){ if(!match) { match =true; } tmpResult.add(a.charAt(indexA)); if(indexA indexA++; } } else{ if(match) { result.add(tmpResult); //重置条件 tmpResult=newArrayQueue(); indexA=i; } } if(j==lengthB-1||i==lengthA-1){ if(!tmpResult.isEmpty()){ result.add(tmpResult); //重置条件 tmpResult=newArrayQueue(); } } } } //取最大的子串 Queue stringResult= Collections.max(result,newOrdering @Override publicintcompare(Queue left, Queue right) { returnInteger.compare(left.size(),right.size()); } }); |
优点
指针移动在循环过程中不会产生多余的临时字符串,如果是substring方案就需要考虑效率了。
相关文章
- java 打印一字符串,并在main()方法内调用它 04-21
- python字符串中的单双引 04-10
- 详解C语言中的字符串拼接(堆与栈) 01-15
- java字符串string,stringbuffer、stringbuilder详解 12-24
- python字符串的使用详解 09-22
- python字符串拼接 + if while for循环例子 08-09