宜昌市城市建设学校网站,怎么判断一个网站做的好,中国建设银行公积金网站,用ps做网站首页顶部图片求最长回文子串
给定一个字符串s#xff0c;找出s中最长的回文子串
回文字符串#xff1a;如果一个字符串的逆序和原始字符串相同#xff0c;则称该字符串为回文字符串。
input#xff1a;s mnbalevelabst;
output#xff1a;balevelab
reason#xff1a;…求最长回文子串
给定一个字符串s找出s中最长的回文子串
回文字符串如果一个字符串的逆序和原始字符串相同则称该字符串为回文字符串。
inputs mnbalevelabst;
outputbalevelab
reason算法思路
定义状态数组dp其中dp【i】【j】表示s[i]到s[j]的字符串是否是回文字符串如果是回文字符串则令dp【i】【j】1如果不是回文字符串则令dp【i】【j】0
如果s[i]s[j],那么只要s[i1]s[j-1]的字符串是回文字符串那么s[i]s[j]的字符串就是回文字符串。反之s[i1]s[j-1]的字符串不是回文字符串那么s[i]s[j]的字符串就不是回文字符串。
如果s[i]s[j],那么只要s[i]s[j]的字符串就一定不是回文字符串。因此状态转移方程为
dp【i】【j】dp【i1】【j-1】s【i】s【j】 0 s【i】s【j】代码如下
//求最长回文字符串
string maxHuiwen(string s)
{int len s.size();int start 0;//最长的回文子串的起始位置int max_length_huiwen 1;//定义状态数组dp 其中dp[i][j]表示s[i]到s[j]的字符串是否是回文字符串//如果是回文字符串则令dp【i】【j】1//如果不是回文字符串则令dp【i】【j】0int dp[50][50] { 0 };for (int j 1; j len; j){for (int i 0; i j; i){if (s[i] s[j]){if (j - i 3){dp[i][j] 1;}else{dp[i][j] dp[i 1][j - 1];//状态转移方程}}if (dp[i][j] 1 (j-i1)max_length_huiwen){max_length_huiwen j - i 1;start i;}}}return s.substr(start, max_length_huiwen);
}void test_maxhuiwen()
{string str mnbalevelabst;cout 最长的回文子串为 maxHuiwen(str) endl;
}代码详解 j1i0不满足s[i] s[j]结束当j2; j2i0 不满足s[i] s[j]i; j2i1 不满足s[i] s[j]结束当前循环j; j3i0 不满足s[i] s[j]i; 一直循环直到如下 j7i5 满足s[i] s[j]记录在案记录回文子数组长度max_length_huiwen j - i 13;start 5; 继续循环到下面如下步骤 一直循环直到如下 j10i2 满足s[i] s[j]记录在案记录回文子数组长度max_length_huiwen j - i 18;start 2; 如此一直到循环结束该记录的所需数据不会再发生改变。 ps今天的内容到这里就结束了谢谢观看
上嘉路
