常见的子字符串算法：
LCS(x,y) = 1+ LCS(x[0...xi-1],y[0...yj-1] if x[xi]==y[yj]
else 0
现在，动态规划解决方案已广为人知。但是我无法找出递归解决方案。如果有多个子字符串，则上述算法似乎失败。
例如：
x = "LABFQDB" and y = "LABDB"
应用上述算法
1+ (x= "LABFQD" and y = "LABD")
1+ (x= "LABFQ" and y = "LAB")
return 0 since 'Q'!='B'
返回的值将是 2，而我应该是 3？
有人可以指定递归解决方案吗？
尽量
避免任何混淆，你问的是longest common substring，而不是longest common subsequence，它们非常相似，但有差异。
The recursive method for finding longest common substring is:
Given A and B as two strings, let m as the last index for A, n as the last index for B.
if A[m] == B[n] increase the result by 1.
if A[m] != B[n] :
compare with A[m -1] and B[n] or
compare with A[m] and B[n -1]
with result reset to 0.
以下是不应用记忆的代码，以便更好地说明算法。
public int lcs(int[] A, int[] B, int m, int n, int res) {
if (m == -1 || n == -1) {
return res;
}
if (A[m] == B[n]) {
res = lcs(A, B, m - 1, n - 1, res + 1);
}
return max(res, max(lcs(A, B, m, n - 1, 0), lcs(A, B, m - 1, n, 0)));
}
public int longestCommonSubString(int[] A, int[] B) {
return lcs(A, B, A.length - 1, B.length - 1, 0);
}
以下是最长公共子字符串的递归代码：
int LCS(string str1, string str2, int n, int m, int count)
{
if (n==0 || m==0)
return count;
if (str1[n-1] == str2[m-1])
return LCS(str1, str2, n-1, m-1, count+1);
return max(count, max(LCS(str1, str2, n-1, m, 0), LCS(str1, str2, n, m-1, 0)));
}
package algo.dynamic;
公共类 LongestCommon子字符串 {
public static void main(String[] args) {
String a = "LABFQDB";
String b = "LABDB";
int maxLcs = lcs(a.toCharArray(), b.toCharArray(), a.length(), b.length(), 0);
System.out.println(maxLcs);
}
private static int lcs(char[] a, char[] b, int i, int j, int count) {
if (i == 0 || j == 0)
return count;
if (a[i - 1] == b[j - 1]) {
count = lcs(a, b, i - 1, j - 1, count + 1);
}
count = Math.max(count, Math.max(lcs(a, b, i, j - 1, 0), lcs(a, b, i - 1, j, 0)));
return count;
}
}
这是我对
最长的常见子字符串问题的递归解决方案。
ans = 0
def solve(i,j,s1,s2,n,m,dp):
global ans
# i is the starting index for s1
# j is the starting index for s2
if(i >= n or j >= m):
return 0
if(dp[i][j] != -1):
return dp[i][j]
if(s1[i] == s2[j]):
dp[i][j] = 1 + solve(i+1,j+1,s1,s2,n,m,dp)
else:
dp[i][j] = 0
solve(i,j+1,s1,s2,n,m,dp)
solve(i+1,j,s1,s2,n,m,dp)
ans = max(ans,dp[i][j]) # ans is storing maximum till now
return dp[i][j]
def longestCommonSubstr(s1, s2, n, m):
global ans
# n is the length of s1
# m is the length s2
dp = [[-1 for i in range(m)] for j in range(n)]
ans= 0
solve(0,0,s1,s2,n,m,dp)
return ans
long max_sub(int i, int j)
{
if(i<0 or j<0)
return 0;
if(s[i]==p[j])
{
if(dp[i][j]==-1)
dp[i][j]=1+max_sub(i-1,j-1);
}
else
{
dp[i][j] = 0;
}
if(i-1>=0 and dp[i-1][j]==-1)
max_sub(i-1, j);
if(j-1>=0 and dp[i][j-1]==-1)
max_sub(i, j-1);
return dp[i][j];
}
您的代码问题似乎您没有尝试所有 n^2 种可能性。
我在 c++ 中为此设计了一个递归解决方案。在我的方法中，我采用一个特定的 i，j，然后如果它们相等，我加 1 并调用 i+1、j+1 的函数，而如果它们不相等，我将在我创建的 2D 数组中的相应 i、j 处存储一个零。执行后，我正在打印 2D 数组，似乎还可以。由于我只是填充 2D 数组，我认为时间复杂度必须为 O(mn(，其中 m 是一个数组的长度，n 是另一个数组的长度。
//Finding longestcommonsubword using top down approach [memoization]
#include<iostream>
using namespace std;
int findlength(char A[], char B[], int i, int j, int st[][5], int r, int c){
if(r <= i)
return 0;
else if(c <= j)
return 0;
else{
if(A[i] == B[j]){
if(st[i][j] == -1)
st[i][j] = 1+findlength(A, B, i+1, j+1, st, r, c);
}else{
st[i][j] = 0;
int a = findlength(A, B, i, j+1, st, r, c);
int b = findlength(A, B, i+1, j, st, r, c);
}
}
return st[i][j];
}
int main(){
int n,m;
cin>>n>>m;
char A[n],B[m];
for(int i = 0;i < n;i++)
cin>>A[i];
for(int j = 0;j < m;j++)
cin>>B[j];
int st[n][5];
for(int k = 0; k < n;k++){
for(int l = 0; l< 5;l++){
st[k][l] = -1;
}
}
findlength(A, B, 0, 0, st, n, 5);
for(int k = 0; k < n;k++){
for(int l = 0; l< 5;l++){
cout<<st[k][l]<<" ";
}
cout<<endl;
}
return 0;
}
int max; //This gloabal variable stores max substring length
int[][]dp; // 2D Array for Memoization
void main(){
//--------Main method just intended to demonstrate initialization---------
dp = new int[m+1][n+1] //m and n are string length
lcs(String a,String b,int n,int m)
}
//---++++++++-----Recrsive Memoized Function------++++++++++++-------
static int lcs(String a,String b,int n,int m){
if(dp[n][m]!=-1)return dp[n][m];
if(n==0||m==0)return dp[n][m]=0;
if(a.charAt(n-1)==b.charAt(m-1))
{
int res=0;int i=n-1,j=m-1;
while((i>=0&&j>=0)&&a.charAt(i)==b.charAt(j)){
res++;
if(i==0||j==0)return dp[n][m] = Math.max(res,max);
i--;j--;
}
max=Math.max(res,max);
return dp[n][m]=Math.max(max,Math.max(lcs(a,b,n-res,m),lcs(a,b,n,m-res)));
}
return dp[n][m]=Math.max(lcs(a,b,n-1,m),lcs(a,b,n,m-1));
}
下面是计算最长公共字符串的递归方法：
public int lcsLength(String x, String y)
{
char[] xc = x.toCharArray();
char[] yc = y.toCharArray();
return lcsLength(xc, xc.length - 1, yc, yc.length - 1, 0);
}
private int lcsLength(char[] xc, int xn, char[] yc, int yn, int currentCsLength)
{
if (xn < 0 || yn < 0) {
return currentCsLength;
}
if (xc[xn] == yc[yn]) {
return lcsLength(xc, xn - 1, yc, yn - 1, currentCsLength + 1);
}
else {
return max(currentCsLength,
max(
lcsLength(xc, xn - 1, yc, yn, 0),
lcsLength(xc, xn, yc, yn - 1, 0)));
}
}
使用此解决方案的缺点是，对于 x 和 y 的相同子字符串，它需要重新计算数倍的公共字符串。
此解决方案使用记忆技术来避免计算递归中最长公共字符串的数倍。
public int lcsLength(String x, String y)
{
char[] xc = x.toCharArray();
char[] yc = y.toCharArray();
Integer[][] memoization = new Integer[xc.length][yc.length];
return lcsLength(xc, xc.length - 1, yc, yc.length - 1, memoization);
}
private int lcsLength(char[] xc, int xn, char[] yc, int yn, Integer[][] memoization)
{
if (xn < 0 || yn < 0) {
return 0;
}
if (memoization[xn][yn] == null) {
if (xc[xn] == yc[yn]) {
// find out how long this common subsequence is
int i = xn - 1, j = yn - 1, length = 1;
while (i >= 0 && j >= 0 && xc[i] == yc[j]) {
i--;
j--;
length++;
}
memoization[xn][yn] = Math.max(length, lcsLength(xc, xn - length, yc, yn - length, memoization));
}
else {
memoization[xn][yn] = max(
lcsLength(xc, xn - 1, yc, yn, memoization),
lcsLength(xc, xn, yc, yn - 1, memoization));
}
}
return memoization[xn][yn];
}
希望这可能会有所帮助，即使有很多答案！
public static int LongestCommonSubString(String x, String y, int m, int n, int curr_max) {
if (m == 0 || n == 0) return curr_max;
if (x.charAt(m - 1) == y.charAt(n - 1)) return LongestCommonSubString(x, y, m - 1, n - 1, curr_max + 1);
return Math.max(LongestCommonSubString(x, y, m - 1, n, 0), LongestCommonSubString(x, y, m, n - 1, 0));
}
递归 + 记忆解决方案;发现所有可能的组合
class Solution{
int[][] t;
int longestCommonSubstr(String s1, String s2, int n, int m){
// code here
t = new int[n+1][m+1];
for(int i = 0; i <=n; i++){
for(int j = 0; j <=m; j++){
t[i][j] = -1;
}
}
for(int i = 0; i<=n; i++){
t[i][0] = 0;
}
for(int j = 0; j<=m; j++){
t[0][j] = 0;
}
solve(s1,s2,n,m);
// for(int i = 0; i <=n; i++){
// for(int j = 0; j <=m; j++){
// System.out.print(t[i][j]+" ");
// }
// System.out.println();
// }
int ans = Integer.MIN_VALUE;
for(int i = 0; i <= n; i++){
for(int j = 0; j <=m; j++){
ans = Math.max(ans,t[i][j]);
}
}
return ans;
}
private int solve(String s1, String s2, int m, int n){
if(m == 0 || n == 0) return 0;
int ans = 0;
if(s1.charAt(m-1) == s2.charAt(n-1)){
if(t[m][n] == -1){
t[m][n] = 1 + solve(s1,s2,m-1,n-1);
}
ans = t[m][n];
}
if(t[m-1][n] == -1)
t[m-1][n] = solve(s1,s2,m-1,n);
if(t[m][n-1] == -1)
t[m][n-1] = solve(s1,s2,m,n-1);
return ans;
}
}
最长公共子字符串的递归和记忆解决方案。
我认为这是你要找的
class Solution {
int ans = 0;
public int findLength(int[] A, int[] B) {
int dp[][] = new int[A.length + 1][B.length + 1];
for (int i = 0; i < A.length + 1; i++)
Arrays.fill(dp[i], -1);
commonSub(A, B, A.length, B.length, dp);
return ans;
}
public int commonSub(int[] x, int[] y, int n, int m, int[][] dp) {
//Base conditon
if (n == 0 || m == 0) return 0;
//Memorisation
if (dp[n][m] != -1) return dp[n][m];
// for traversing the whole string n*m
commonSub(x, y, n, m - 1, dp);
commonSub(x, y, n - 1, m, dp);
if (x[n - 1] == y[m - 1]) {
dp[n][m] = commonSub(x, y, n - 1, m - 1, dp) + 1;
ans = Math.max(ans, dp[n][m]);
return dp[n][m];
}
return dp[n][m] = 0;
}
}
3 变量记忆索引 1 和索引 2 和计数(因为我们携带计数也(
import java.util.*;
import java.io.*;
public class Solution {
public static int lcs(String str1, String str2) {
int l1 = str1.length(), l2 = str2.length(), lmin = Math.min(l1, l2);
int[][][] dp = new int[l1][l2][lmin];
// filling 3d matrix dp with -1 for not visted
for (int[][] mat: dp) {
for (int[] row: mat)
Arrays.fill(row, -1);
}
// max unit array just for storing max value in traversal
int[] max = {0};
lcsUtil(dp, max, str1, str2, l1 - 1, l2 - 1, 0);
//returning maximum we caputured in the traversal
return max[0];
}
static int lcsUtil(int[][][] dp, int[] max, String s1, String s2, int l1, int l2, int cnt) {
if (l1 < 0 || l2 < 0)
return cnt;
if (dp[l1][l2][cnt] != -1)
return dp[l1][l2][cnt];
int x1 = 0, x2 = 0, x3 = 0;
x1 = lcsUtil(dp, max, s1, s2, l1 - 1, l2, 0);
x2 = lcsUtil(dp, max, s1, s2, l1, l2 - 1, 0);
if (s1.charAt(l1) == s2.charAt(l2)) {
x3 = lcsUtil(dp, max, s1, s2, l1 - 1, l2 - 1, cnt + 1);
max[0] = Math.max(max[0], cnt + 1);
}
return dp[l1][l2][cnt] = Math.max(x3, Math.max(x1, x2));
}
}
我在这里尝试了一些代码，但仍然感到困惑。使用此输入
hellothelo heisahello
该算法首先检查"Lo"，然后继续检查索引 8 中的最长子字。此输入的最终答案是 2，但"hello"的预期答案是 5。
我在这里做错了什么吗？
尝试过这个，看起来正在工作
int lcw(string a, string b, int i, int j, int count){
if (i>=a.size() || j>=b.size()) return count;
if (a[i] == b[j]){
return max(max(lcw(a, b, i, j+1, 0), lcw(a, b, i+1, j, 0)), lcw(a, b, i+1, j+1, count+1));
}
else {
return max(count, max(lcw(a, b, i, j+1, 0), lcw(a, b, i+1, j, 0)));
}
}
我觉得下面的算法是错误的
int lcw(string str1, string str2, int n, int m, int count)
{
if (n==0 || m==0)
return count;
if (str1[n-1] == str2[m-1])
return lcw(str1, str2, n-1, m-1, count+1);
return max(count, max(lcw(str1, str2, n-1, m, 0), lcw(str1, str2, n, m-1, 0)));
}
是一旦我们找到相等的东西，我们就会继续两个字符串中的下一个字符，但错过了可能有更大字符串的可能性。
下面是代码，但我想它不是 O(mn(
class Solution:
def __init__(self):
self.memo={}
def longestCommonSubstr(self, S1, S2, n, m):
def f(i,j):
if (i,j) in self.memo:
return self.memo[(i,j)]
if i<0 or j<0:
return 0
if S1[i]==S2[j]:
t=1+f(i-1,j-1)
self.memo[(i,j)]=t
return t
else:
self.memo[(i,j)]=0
return 0
maxm=0
for i in range(n-1,-1,-1):
for j in range(m-1,-1,-1):
if (i,j) in self.memo:
maxm=max(maxm,self.memo[(i,j)])
else:
maxm=max(maxm,f(i,j))
return maxm
import sun.jvm.hotspot.types.CIntegerType;
class RespObject {
public int len;
public boolean isSubString;
int maxLen;
public RespObject(int len, boolean isSubString, int maxLen) {
this.maxLen = maxLen;
this.len = len;
this.isSubString = isSubString;
}
}
public class LongestCommonSubstring {
public static void longestCommonSubstring(String str1, String str2, int i, int j, RespObject resp) {
if ((j == str2.length()) || (i == str1.length())) {
resp.isSubString = false;
resp.len = 0;
return;
}
int currLen = 0;
longestCommonSubstring(str1, str2, i + 1, j, resp);
RespObject respObject1 = resp;
longestCommonSubstring(str1, str2, i, j + 1, resp);
RespObject respObject2 = resp;
if (str1.charAt(i) == str2.charAt(j)) {
longestCommonSubstring(str1, str2, i + 1, j + 1, resp);
resp.len += 1;
currLen = resp.len;
resp.isSubString = true;
} else {
resp.len = 0;
resp.isSubString = false;
}
resp.maxLen = Integer.max(Integer.max(respObject1.maxLen, respObject2.maxLen), currLen);
}
public static void main(String[] args) {
RespObject respObject = new RespObject(0, false, Integer.MIN_VALUE);
longestCommonSubstring("dSite:Geeksf", "wSite:GeeksQ", 0, 0, respObject);
System.out.println(respObject.len + " " + String.valueOf(respObject.isSubString) + " " + respObject.maxLen);
}
}