最长公共子串的方法-Java 学习之路

在Common Child中的编程挑战中，我采用了与一般最长公共子串问题不同的方法 . 守则是

#include <cmath>
#include <cstdio>
#include <vector>
#include<string>
#include <iostream>
#include <algorithm>
using namespace std;

void max(string a,string b,int n)
{
    int count=0,x=-1,prev=0,i,j,k;
    for(i=0;i<n;i++)
    {
        x=-1;
        for(j=i;j<n;j++)
        {
            for(k=x+1;k<n;k++)
            {
                if(a[j]==b[k])
                {
                    count++;
                    x=k;
                    break;
                }
            }
        }
        if(prev<count)
        {
            prev=count;
        }
        count=0;        
    }
    cout<<prev;
}

int main() {
    string a,b;
    int n;
    cin>>a;
    cin>>b;
    n=a.length();
    max(a,b,n);
    return 0;

采用较小的TestCases我能够获得解决方案，但我无法获得更长的解决方案 .

我做的是

输入：ABCDEF - 让它成为FBDAMN - 让它成为b，因为它插入代码中 . 输出：2 . 即 . 因为BD是子串 . 所以我在这里做的是检查a的每个子字符串的匹配子字符串，并打印最大的子字符串 . 即 . ABCDEF的子串，BCDEF，CDEF，DEF，EF，F，这里表示最外层的循环 . （循环i）现在，第二个循环匹配字符串中的每个字母，即 . 它迭代为（1 ... n），（2 ... n），（3 ... n），...，（n），意味着它从我指定的字母开始 . 现在第三个循环遍历整个字符串B以查看[j]是否与B中的任何字母匹配，如果是，则计算增量 . 因为我们只能从子字符串中删除字母而不是混淆它，即每个字母在两个字符串中应该具有相同的相对顺序，我在使用x找到上一个字母后搜索B.干运行就像示例（数组从0到n-1）a = abcdef b = fbdamn当i = 0时 - 整个字符串匹配abcdef x = -1所以k从0迭代到n-1所以，一= F？ A = B？ A = d？ A = A？ count = count 1;所以x设置为3（a的位置） . 在A中a之后的元素只能在a中出现，因此x = 3 . 因此k迭代从4到5 b = m？ B = N + C = M + C = N？ .... ... ...现在我们保存先前计数的值，如果它大于之前的计数 . 所以maxcount = count然后重置count到0，并重置位置x = -1 . i = 1，即string = BCDEF k从0到n所以，B = F？ B =？ count = count 1 //变为1 x被设置为1（B的位置）k从2到n c = d？ C = A C = M + C = N？ k从2到n d = d？ count = count 1 //变为2 x被设置为3 k从3到n e = a？e = m？e = n？ k从3到n f = a？f = m？f = n？然后，如果最大计数（代码中的prev）大于当前计数，则maxcount = count，reset count = 0，x = -1;然后它就像CDEF，DEF，EF，F这样，这里的最大子串变为2适用于较短的测试用例而不适用于较长的测试用例 .

它适用的测试用例是：

OUDFRMYMAW AWHYFCCMQX

输出2

不起作用

WEWOUCUIDGCGTRMEZEPXZFEJWISRSBBSYXAYDFEJJDLEBVHHKS FDAGCXGKCTKWNECHMRXZWMLRYUCOCZHJRRJBOAJOQJZZVUYXIC

正确的输出为 15 ，输出为 10 . 任何人都可以向我解释我在哪里弄错了

3 回答

6
问题是你的算法使用了一种天真的贪婪方法：它在看到它后立即进行匹配，并且在此之后再也不会重新考虑它的决定，直到它到达下一个子串 . 可以通过反例证明这种贪婪策略不适用于LCS：考虑字符串
```
A = "abcd"
B = "acdb"
```
你的算法returns 2因为它资助 "ab" ，而最长的子序列是 "acd" ，长度为3 .

这两个字符串经过精心构造，可以欺骗您的算法产生错误的结果 . 您的算法将匹配初始位置的 'a' ，前进到字符串 A 的第二个字符 'b' ，并在字符串 B 的最后位置匹配它 . 此时，您的算法注定失败：它找不到 'c' 和 'd' ，因为 B 的所有字符都已用尽 . 它本应该做的就是通过回溯匹配 'b' 的决定，好像它可以做得更好 . 这个问题的答案是响亮的"yes"：如果我们跳过 A 的第二个字符，我们将匹配 'c' 和 'd' ，以获得正确的3结果 .

LCS的正确实现（使用DP或带有memoization）可以实现这种回溯，而不会以指数方式增加时间 . 它是研究和实现的最简单的DP算法之一，因此您可以毫无困难地应用它来解决手头的问题 .
回复于 2024-04-29T20:36:06+08:00
4

我预见的一个问题如下：

如果a = ABCDEFG且b = ACDEFGB，

现在它将首先匹配A，然后它将匹配B，但是k已经变为6 . 因此，CDEFG的其他字母将不会匹配 .

因此，应跳过可能的字符串ACDEFG .

您的代码应将最大公共子项作为CDEFG返回 .

EDIT: This is not a longest common substring problem but a longest common subsequence problem. http://www.geeksforgeeks.org/dynamic-programming-set-4-longest-common-subsequence/

回复于 2024-04-29T20:36:06+08:00

import java.util.Scanner;
  public class JavaApplication8 {
      public static int find(String s1,String s2){
        int n = s1.length();
        int m = s2.length();
        int ans = 0;
        int[] a = new int[m];
        int b[] = new int[m];
        for(int i = 0;i<n;i++){
            for(int j = 0;j<m;j++){
                if(s1.charAt(i)==s2.charAt(j)){
                   if(i==0 || j==0 )a[j] = 1;
                   else{
                       a[j] = b[j-1] + 1;
                   }
                   ans = Math.max(ans, a[j]);
                }

            }
            int[] c = a;
            a = b;
            b = c;
        }
        return ans;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s1 = sc.next();
        String s2 = sc.next();
        System.out.println(find(s1,s2));
    }

}

Time Complexity O(N). Space Complexity O(N).

回复于 2024-04-29T20:36:06+08:00

最长公共子串的方法

3 回答

相关问题