计算两个字符串最大公有子串
背景 对算法一直应用的比较少,最近看到一些典型的算法想练练手,想看看到底有多么让人讨厌。其实发现算法都有一定的套路,一般并不是临时凭空想出来的,大都建立在一些已经存在的经典算法知识以及数据结构上。换句话来说,如果某些玩法之前未接触过,那么让你在短时间内临时想出来还是有一定难度的。这有点类似项目经验,如果曾经做过一个CRM系统,下次再碰到它时你就轻松很多,如果你挑战的是一个你从未遇到过的系统,你只能凭已有知识去强吃。 计算两个字符串最大公共子串 这个也是经常遇到到,给出两个任意长度的字符串,输出最大公有字符串,比如输入abcdef,cdef,则输出cdef。 解决方案 采用双层循环,指针移动来记录所有子串,最后取最大长度子串。利用临时队列来存储循环过程中匹配成功的字符元素,从两个字符串首个元素开始匹配。
示意图 从元素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方案就需要考虑效率了。 以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,同时也希望多多支持编程小技巧! (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |
- Java属性文件中equals和冒号之间的区别
- 10-05 Java 内部类概述和讲解
- 无法在java中对SSL站点进行身份验证:“违反了pathLenConst
- java – 练习递归和OO设计的任何网站/书籍/技巧?
- java – LWJGL 3获取光标位置
- .net – 用字符串初始化的StringBuilder是否包含该字符串的
- Spring boot集成Kafka+Storm的示例代码
- java – Spring,@Transactional和Hibernate Lazy Loading
- java – 如何使用Spring MVC和Spring Security为资源处理程
- java – 尝试做滑动窗口