2

在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;

采用较小的测试用例我能够获得解决方案，但我无法获得更长的解决方案。

我所做的是

输入：ABCDEF - 设为 FBDAMN - 设为 b，因为它已插入代码中。输出：2。即。因为 BD 是子字符串。

所以我在这里做的是检查a的每个子字符串的可匹配子字符串，并打印最大的。IE。ABCDEF, BCDEF,CDEF,DEF,EF,F 的子字符串，表示此处的最外层循环。（循环 i）

现在第二个循环匹配字符串中的每个字母，即。它迭代 (1...n),(2...n),(3...n),...,(n)，这意味着它从 i 指定的字母开始。

现在第三个循环遍历整个字符串 B 以查看 a[j] 是否与 B 中的任何字母匹配，如果是，则 count 递增。

由于我们只能从子字符串中删除字母而不是弄乱它，即每个字母在两个字符串中应该具有相同的相对顺序，因此我在找到前一个字母后使用 x 搜索 B。

试运行就像示例（从 0 到 n-1 的数组）

a= abcdef b= fbdamn

当 i=0 - 整个字符串匹配 abcdef

x=-1 所以 k 从 0 迭代到 n-1 所以，a=f？a=b？a=d? 一个=一个？计数=计数+1；所以x设置为3（a的位置）。A 中的 a 之后的元素只能出现在 B 中的 a 之后，因此 x=3。因此 k 从 4 迭代到 5 b=m？b=n? c=m?c=n? ………………

现在我们保存先前计数的值，如果它大于之前的计数。所以 maxcount=count 然后将 count 重置为 0，并重置位置 x=-1。

i=1 即字符串 = BCDEF k 从 0 到 n 所以，B=F？b=b？count=count+1 // 变为 1 x 设置为 1(B 的位置) k 从 2 到 nc=d? c=a?c=m?c=n? k 从 2 到 nd=d？count = count+1 // 变为 2 x 设置为 2 k 从 3 到 ne=a?e=m?e=n? k 从 3 到 nf=a?f=m?f=n? 然后如果最大计数（代码中的prev）大于当前计数，则maxcount = count，重置count = 0，x = -1；然后对于 CDEF,DEF,EF,F 就这样了，这里的最大子字符串变成了 2

适用于较短的测试用例，但不适用于较长的测试用例。

它适用的测试用例是：

OUDFRMYMAW AWHYFCCMQX

带输出 2

不适合

WEWOUCUIDGCGTRMEZEPXZFEJWISRSBBSYXAYDFEJJDLEBVHHKS FDAGCXGKCTKWNECHMRXZWMLRYUCOCZHJRRJBOAJOQJZZVUYXIC

正确的输出是15，我的输出是10。任何人都可以向我解释我在哪里犯了错误

4

3 回答 3

6

我预见的一个问题如下：

如果 a = ABCDEFG 且 b = ACDEFGB，

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

因此应该跳过可能的字符串 ACDEFG。

您的代码应返回最大的共同子项作为 CDEFG。

编辑：这不是最长的公共子串问题，而是最长的公共子序列问题。http://www.geeksforgeeks.org/dynamic-programming-set-4-longest-common-subsequence/

于 2013-12-20T17:07:51.790 回答
4

问题是您的算法使用了一种幼稚的贪婪方法：它一看到它就进行匹配，之后不再重新考虑它的决定，直到它到达下一个子字符串。可以用一个反例来证明这种贪婪策略不适用于LCS：考虑字符串

A = "abcd"
B = "acdb"

您的算法返回 2，因为它资助"ab"，而最长的子序列是"acd"，长度为 3。

这两个字符串经过精心构造，以欺骗您的算法产生不正确的结果。您的算法将'a'在初始位置匹配 s，前进到 string 的第二个字符'b'，A然后在 string 的最后一个位置匹配它B。在这一点上，你的算法注定要失败：它找不到'c'and 'd'，因为所有字符B都用尽了。它应该做的是，通过回溯匹配的决定，它似乎可以做得更好'b'。这个问题的答案是响亮的“是”：如果我们跳过 的第二个字符A，我们将同时匹配'c'和'd'，以得到 3 的正确结果。

LCS 的正确实现（使用 DP 或使用 memoization）可以在不以指数方式增加时间的情况下进行这种回溯。它是学习和实现的最简单的 DP 算法之一，因此您应该可以毫不费力地应用它来解决手头的问题。

于 2013-12-20T17:33:59.010 回答
0 
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).

于 2018-04-11T17:43:37.727 回答