提问者:小点点

最长公用子字符串多次跳过字符[closed]


我想找到最长的公共子字符串,现在错误地,一个字符已经输入到一个字符串中,我应该跳过一个字符来找到最长的公共子字符串,这样AABB和AACB,其中c是错误的字符,必须跳过。 我试着创建一个相同的dp问题,但是它一个接一个地跳过每个字符

下面给出了我的代码,它满足了这个目的,但是跳过了每个字符,而不是只跳过一个字符,我希望代码只跳过一个:测试用例是AABB和AACB,在特定的情况下,我希望它只跳过c一次。

    #include <iostream.h>    
    #include<string.h> 
    using namespace std;   
    int LCSubStr(char *X, char *Y, int m, int n) 
    {  
        int LCSuff[m+1][n+1]; 
        int result = 0;  
        bool flag=false;
        for (int i=0; i<=m; i++) 
        {   
            for (int j=0; j<=n; j++) 
            {   
                if (i == 0 || j == 0) 
                    LCSuff[i][j] = 0; 
                        
                else if (X[i-1] == Y[j-1]) 
                { 
                    LCSuff[i][j] = LCSuff[i-1][j-1] + 1; 
                    result = max(result, LCSuff[i][j]); 
                } 
                
          else if((X[i-2] == Y[j-1] || X[i-1] == Y[j-2])  && X[i-1] != Y[j-1] )
          {
         
                LCSuff[i][j] = LCSuff[i-1][j-1] + 1; 
                    result = max(result, LCSuff[i][j]); 
          }
                         
        else 
        {
                LCSuff[i][j] = 0; 
                
        }
            }
              
        } 
         
        return result; 
   } 

int main() 
{ 
    char X[] = "AABB"; 
    char Y[] = "AABB";
    int m = strlen(X); 
    int n = strlen(Y); 
    cout << "Length of Longest Common Substring is "<< LCSubStr(X, Y, m, n); 
    return 0; 
} 

共1个答案

匿名用户

int LCSubStr(char *X, char *Y, int m, int n) 
    {    
        int LCSuff[m+1][n+1]={0}; 
        for (int i=1; i<=m; i++) 
        { 
            for (int j=1; j<=n; j++) 
            {      
                
                if(X[i-1] == Y[j-1]) 
                { 
                    LCSuff[i][j] = LCSuff[i-1][j-1] + 1; 
                    
                } 
                  else 
                {
                  LCSuff[i][j] = max(LCSuff[i-1][j], LCSuff[i][j-1]);
                }
            }         
        } 
        return LCSuff[m][n];
    }