运行测试用例时出现错误 In LONGEST COMMON SUBSTRING

Question

我需要解决一个问题，要求代码找到 2 个字符串之间的最长公共子串：

我的代码没有针对下面给出的一个测试用例运行：

17 60
KXCGMTMVVGFQQWSPD
JXZADDUKVLQPKUZJZHWSUTPCAFSYAIBJHAMMEGWBTPQELRNKBLDXGUZGCSEC

代码如下

//{ Driver Code Starts
#include<bits/stdc++.h>
using namespace std;

// } Driver Code Ends
class Solution{
    public:
    // This is the recursive approach 
    int longest( string s1 , string s2  , int i,  int j , int & ans ,vector<vector<int>> &dp  )
    {
        if(i<0 && j<0)
        {
            return 1;
        }
        if(i<0|| j<0)
        {
            return 0;
        }
        if(dp[i][j]!=-1)
        {
            return dp[i][j];
        }
        if(s1[i]==s2[j])
        {
            int k = 1+longest(s1,s2 ,i-1 ,j-1 ,ans ,dp);
            ans = max(ans, k);
            dp[i][j]=k ;
            return k ;
        }
        int a =longest(s1, s2 , i-1,j , ans,dp);
        int b = longest(s1,s2 ,i ,j-1,ans,dp) ;
        dp[i][j]=0;
        return 0;
    }
     // Here is the tabulation approach 
    int longestCommonSubstr (string s1, string s2, int n, int m)
    {
        // your code here
        int ans=0;
        vector<vector<int>> dp (s1.length(),vector<int>( s2.length(),-1));
        int k = longest(s1,s2,n-1,m-1,ans,dp);
        return ans;
        /*int ans =0;
        vector<int> row1(s2.length()+1 ,0);
        vector<int> row2(s2.length()+1 , 0);
        for( int i =0;i<n ;i++)
        {
            for( int j =0;j<m ;j++)
            {
                if(s1[i]==s2[j])
                {
                    int k =1+row1[j];
                    ans = max(ans,k);
                    row2[j+1]=k; 
                }
                else
                {
                    row2[j+1]=0;
                }
            }
            row1= row2 ;
        }
        return ans;*/
    }
};

//{ Driver Code Starts.

int main()
{
    int t; cin >> t;
    while (t--)
    {
        int n, m; cin >> n >> m;
        string s1, s2;
        cin >> s1 >> s2;
        Solution ob;

        cout << ob.longestCommonSubstr (s1, s2, n, m) << endl;
    }
}
// Contributed By: Pranay Bansal

// } Driver Code Ends

我已经尝试过，但是其中一个测试用例的记忆技术失败了，但是制表技术确实有效。所以请大家参考代码改正。

Answer 1

我仍然没有达到 C++ 中的类之类的水平，但是对于这个测试用例，似乎有一个与您不同的更简单的解决方案。我的代码保证可以工作，即使它可能很慢，因为它使用蛮力检查较短字符串的每个子字符串（检查较长的字符串需要时间并且子字符串可能比较短的字符串长，从而产生错误）。但是，我试图通过检查具有向后大小的较短字符串来加快它的速度，以找到两者中共有的第一个字符串，这也是最大的公共子字符串。这意味着代码不再需要我的循环运行更多次。您的测试用例在合理的时间限制内运行并在此处获得正确的结果：在页面底部使用您的测试用例运行演示

#include <iostream>
#include <string>
int discard; //you can access string length using the function
std::string str1, str2, temp;
int main () {
    std::cin >> discard >> discard >> str1 >> str2;
    if (str1.length() > str2.length()) {//if str1 is not the shorter one, make it the shorter one by switching
        temp = str2;
        str2 = str1;
        str1 = temp;
    }
    for (int size = str1.length(); size >= 1; size--) { //backwards length checking
        for (int j = 0; j <= str1.length() - size; j++) { //start position
            temp = str1.substr(j, size); //the substring
            if (str2.find(temp) != std::string::npos) { //if the substring works, it is the largest
                std::cout << "The longest common substring: " << temp; //output and end program
                return 0;
            }
        }
    }
    std::cout << "No Common Substring";
    return 0;
}