#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int findpali (string s,int dp[][100],int st, int e);
int main (void)
{
string s;
cin>>s;
int dp[100][100];
for (int i = 0; i < 100; i++ )
for ( int j = 0; j < 100; j++ )
dp[i][j] = -1;
int out = findpali(s,dp,0,s.length()-1);
cout<<out<<"\n";
return 0;
}
int findpali (string s,int dp[][100],int st, int e) // st ->starting position, e -> ending position
{
if (s.length() == 1)
{
dp[st][e] = 1;
return 1;
}
else if (s.length()==2 && s[st] == s[e])
{
dp[st][e] = 2;
return 2;
}
else if (dp[st][e] != -1)
return dp[st][e];
else if (s[st] == s[e])
{
dp[st][e] = findpali(s.substr(st+1,s.length()-2),dp,st+1,e-1)+2;
return dp[st][e];
}
else
{
dp[st][e] = max(findpali(s.substr(st,s.length()-1),dp,st,e-1),findpali(s.substr(st+1,s.length()-1),dp,st+1,e));
return dp[st][e];
}
}
上述函数找出给定字符串中最长回文的长度。我已将给定数组 dp
初始化为 -1
,然后我将不同的值存储在数组中。但是,当我输入类似 ABCD
的字符串时,它会显示超出范围的异常并中止。这可能是什么原因?谢谢!
最佳答案
您需要在函数的开头添加空字符串测试。此外,您正在为原始 string s
存储 dp
,因此当您使用 s 的子字符串更新它时,结果不再有效。每次递归调用该函数时,您只需传递不同的索引 st 和 e
。
您修改后的函数可能看起来像这样:
int findpali(string &s, int dp[][100], int st, int e)
{
if(s.length()==0 || st > e) { //extra test for boundary case
return 0;
}
if(st==e) // length 1 substring
{
dp[st][e]=1;
return 1;
} else if(e-st==1 && s[st] == s[e]) // length 2 substring
{
dp[st][e]=2;
return 2;
} else if(dp[st][e] != -1)
return dp[st][e];
else if(s[st] == s[e])
{
dp[st][e]=findpali(s, dp, st+1, e-1)+2;
return dp[st][e];
} else
{
dp[st][e]=max(findpali(s, dp, st, e-1), findpali(s, dp, st+1, e));
return dp[st][e];
}
}
关于c++ - 为什么我在这个函数中会出现越界异常?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/31889473/