我想找到最长的公共子字符串,现在错误地,一个字符已经输入到一个字符串中,我应该跳过一个字符来找到最长的公共子字符串,这样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;
}
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];
}