对于两个字符串,请设计一个时间复杂度为O(m*n)的算法(这里的m和n为两串的长度),求出两串的最长公共子串的长度。这里的最长公共子串的定义为两个序列U1,U2,..Un和V1,V2,...Vn,其中Ui + 1 == Ui+1,Vi + 1 == Vi+1,同时Ui == Vi。
给定两个字符串A和B,同时给定两串的长度n和m。
测试样例:
"1AB2345CD",9,"12345EF",7
返回:4
import java.util.*; public class LongestSubstring { public int findLongest(String A, int n, String B, int m) { int res = 0; int[][] dp = new int[A.length()][B.length()]; for (int i = 0; i < A.length(); i++) { if (A.charAt(i) == B.charAt(0)) { dp[i][0] = 1; } } for (int i = 1; i < B.length(); i++) { if (A.charAt(0) == B.charAt(i)) { dp[0][i] = 1; } } for (int i = 1; i < A.length(); i++) { for (int j = 1; j < B.length(); j++) { if (A.charAt(i) == B.charAt(j)) { dp[i][j] = dp[i-1][j-1] + 1; } } } for (int i = 0; i < dp.length; i++) { for (int j = 0; j < dp[0].length; j++) { if (res < dp[i][j]) { res = dp[i][j]; } } } return res; } }
相关推荐
最长公共子串的快速搜索算法 最长公共子串的快速搜索算法 最长公共子串的快速搜索算法
最长公共子串求解,有需要的可以下来参考……
用定长顺序存储结构表示串: (1) 建立两个文本文件,分别存储串str1“hellohisgoodl”和串str“hellogdygoodl” (2) 输出两个串的最长公共子串“hello”和“goodl”; (3) 分析算法时间复杂度。
大整数计算器最长公共子串数据结构课设,沈阳工程学院
本文实例讲述了C语言求两个字符串的最长公共子串的方法。分享给大家供大家参考。具体实现方法如下: #include "stdio.h" #include "string.h" #include "stdlib.h" void getCommon(char str1[],char str2[],char * ...
本文实例讲述了JavaScript自定义函数实现查找两个字符串最长公共子串的方法。分享给大家供大家参考,具体如下: //查找两个字符串的最长公共子串 function findSubStr(s1,s2){ var S=sstr= ,L1=s1.length,L2=s2....
查找两个字符串a,b中的最长的公共子串,并将结果输出
动态规划:最长公共子串 LCS 动态规划:最长公共子串 LCS
求解最大子序列、最长递增子序列、最长公共子串、最长公共子序列. http://blog.csdn.net/ssuchange/article/details/17341693
用本程序可得到字符串的相似度和字符串的公共子串以及编辑距离。
MFC实现数据结构的简单问题,最长公共子串,界面良好,算法简单
自己写的最长公子串算法,没有参考网上的代码。
c源码编写的求两个字符串的最长公共子串,采用递归算法
用Python实现动态规划中最长公共子序列和最长公共子串问题!
请编写一个函数,输入两个字符串,求它们的最长公共子串,并打印出最长公共子串。例如:输入两个字符串BDCABA和ABCBDAB,字符串BCBA和BDAB都是是它们的最长公共子串,则输出它们的长度4,并打印任意一个子串。 分析...
求N个字符串的最长公共子串,N,字符串长度不超过255。例如N=3,由键盘依次输入3个字符串为 Whatislocalbus? Namesomelocalbuses. loca1busisahighspeedI/Obusclosetotheprocessor. 则最长公共子串为“local...
主要介绍了java实现求两个字符串最长公共子串的方法,是一道华为OJ上的一道题目,涉及Java针对字符串的遍历、转换及流程控制等技巧,需要的朋友可以参考下
主要介绍了PHP实现求两个字符串最长公共子串的方法,涉及php字符串与数组的遍历、运算、判断等相关操作技巧,需要的朋友可以参考下
最长公共子串(The Longest Common Substring) LCS问题就是求两个字符串最长公共子串的问题。解法就是用一个矩阵来记录两个字符串中所有位置的两个字符之间的匹配情况,若是匹配则为1,否则为0。然后求出对角线最长的1...