最长公共子串的探讨

Question

在普通儿童的编程挑战中，我采取了与一般最长的公共子串问题不同的方法。守则是

#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的子字符串。 现在，第二个循环匹配字符串中的每个字母。它迭代(1.n)，(2.n)，(3.n)，.，(n)，意味着它从i指定的字母开始。 现在，第三个循环遍历整个字符串B，查看aj是否与B中的任何字母匹配，如果是，则计数增量。 因为我们只能从子字符串中移除字母，而不能混淆它，也就是说，每个字母在两个字符串中都应该有相同的相对顺序，所以在找到前一个字母之后，我使用x搜索B。 这个示例类似于试运行(数组从0到n-1)。 a= abcdef b= 当i=0 -整个字符串得到匹配时 X=-1sok从0到n-1so，a=f？a=b？a=d？a=a？count = count+1；so x设置为3(a的位置)。A in A之后的元素只能出现在a in B之后，所以x=3。因此k从4到5 b=m？b=n？c=m?c=n？..。... ... 现在，如果以前的计数大于以前的计数，则保存它的值。因此，maxcount=count，然后重置计数为0，并重置位置x=-1. i=1 I.String=B=F k从0到n，B=F？b=b？count=count+1 //变成1x被设为1(B的位置)k从2到n c=d？c=a?c=m?c=n？K从2到n d=d？count = count+1 //成2x被设置为从3到n e=a?e=m?e=n的2k？K从3到n f=a?f=m?f=n？如果max计数(代码中的prev)大于当前计数，则maxcount = count，重置计数= 0，x=-1；那么对于CDEF，DEF，EF，F，这里的max子字符串将变成2。 适用于较短的测试案例，而不是较长的测试案例。

它工作的测试用例如下：

OUDFRMYMAW AWHYFCCMQX

输出2

不工作

WEWOUCUIDGCGTRMEZEPXZFEJWISRSBBSYXAYDFEJJDLEBVHHKS FDAGCXGKCTKWNECHMRXZWMLRYUCOCZHJRRJBOAJOQJZZVUYXIC

正确的输出是15，我的输出是10。有人能向我解释我在哪里犯了错误吗？

Answer 1

问题是，您的算法使用了一种天真的贪婪方法:它一看到就进行匹配，然后再考虑它的决定，直到它到达下一个子字符串为止。可以通过一个反例演示这种贪婪的策略不适用于LCS：考虑字符串

A = "abcd"
B = "acdb"

您的算法报税表2是因为它为"ab"提供资金，而最长的子序列是"acd"，长度为3。

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

LCS的适当实现(包括DP或回忆录)可以在没有成倍增长的情况下进行回溯。它是学习和实现最简单的DP算法之一，所以应用它来解决手头的问题应该不会有任何困难。

Answer 2

我预见的一个问题是：

如果a= ABCDEFG和b= ACDEFGB，

现在它将首先匹配A，然后它将匹配B，但随后k将变成6。因此，更多的信CDEFG将不会匹配。

因此，可能的字符串ACDEFG将被跳过。

您的代码将以CDEFG的形式返回最大的普通子程序。

编辑:这不是一个最长的公共子字符串问题，而是一个最长的公共子序列问题。

Answer 3

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).