怎么把自己做的网站发布到网上,建个静态网站,line 设计网站,注册一个公司需要什么问题描述
“回文串”是一个正读和反读都一样的字符串#xff0c;比如“level”或者“noon”等等就是回文串。给你一个字符串#xff0c;问最少在字符串尾添加多少字符#xff0c;可以使得字符串变为回文串。
输入格式
有多组测试数据。
每组测试数据第一行是一个正整数N…问题描述
“回文串”是一个正读和反读都一样的字符串比如“level”或者“noon”等等就是回文串。给你一个字符串问最少在字符串尾添加多少字符可以使得字符串变为回文串。
输入格式
有多组测试数据。
每组测试数据第一行是一个正整数N表示字符串长度接下来一行是长度为N的字符串字符串中只有小写字母。
N0表示输入结束并且不需要处理。
40%的数列元素个数N 1 ≤ N≤ 100
30%的数列元素个数N 1 ≤ N≤ 1000
20%的数列元素个数N 1 ≤ N≤ 10000
10%的数列元素个数N 1 ≤ N≤ 100000
输出格式 对于每组测试数据输出一个非负整数添加最少的字符数可以使得字符串变为回文串。
样例输入 3
aba
4
aaac
0
样例输出 0
3
【算法思想】 动态规划数组初始化创建了一个二维数组 dp大小为 n x n其中 dp[i][j] 表示子串 s[i..j] 是否是回文串的长度。 对角线初始化将对角线上的元素 dp[i][i] 初始化为 1表示单个字符本身就是回文串。 动态规划计算使用两个嵌套的循环从字符串末尾开始遍历所有子串。在这个过程中你检查字符是否相等然后根据不同情况更新 dp[i][j] 的值。具体来说 如果 s[i] s[j]有以下两种情况 当 j - i 1 时表示当前子串的长度为 2 或者 1因此直接将 dp[i][j] 设置为 j - i 1。当 j - i 1 时你检查 dp[i 1][j - 1] 是否表示的子串是回文串如果是则更新 dp[i][j] 为 dp[i 1][j - 1] 2表示当前子串的长度为内部回文子串的长度加上 2。 状态转移方程的核心思想是通过计算已知较短子串的回文信息来推导出更长子串的回文信息。的状态转移方程基于如下考虑 当 s[i] s[j] 时如果 j - i 1则当前子串长度为 2 或 1因此是回文串直接将 dp[i][j] 设置为 j - i 1。当 s[i] s[j] 且 j - i 1 时首先检查 dp[i 1][j - 1] 是否表示的子串是回文串。如果是说明当前子串也是回文串因此更新 dp[i][j] 为 dp[i 1][j - 1] 2表示当前子串的长度为内部回文子串的长度加上 2。
if (s[i] s[j]) {if (j - i 1) {dp[i][j] j - i 1;} else if (dp[i 1][j - 1]) {dp[i][j] dp[i 1][j - 1] 2;}
}这个方程的含义是如果当前子串的两端字符相等那么要判断该子串是否为回文串首先考虑 j - i 1 的情况如果成立说明子串长度为 2 或 1是回文串直接标记长度否则考虑 dp[i 1][j - 1] 是否为回文串如果是那么当前子串也是回文串长度为内部回文子串的长度加上 2。
#includeiostream
#includecstring
#includevector
#includealgorithm
using namespace std;int main()
{int n;while(cin n n ! 0) // 循环读取测试数据直到 n 为 0 结束{string s;cin s; // 读取输入的字符串string x s; // 创建一个与输入字符串相同的副本 xreverse(x.begin(), x.end()); // 将副本 x 反转if (x s) // 如果副本 x 和原始字符串 s 相同说明已经是回文串{cout 0 endl; // 输出结果为 0无需添加字符}else{vectorvectorint dp(n, vectorint(n, 0)); // 创建一个二维数组 dp用于动态规划for (int i 0; i n; i){dp[i][i] 1; // 对角线上的元素置为 1表示单个字符本身是回文串}int max 0; // 用于记录最大的回文子串长度for (int i s.size() - 1; i 0; i--) // 从字符串末尾开始向前遍历{for (int j i; j s.size(); j) // 在 i 到字符串末尾范围内遍历{if (s[i] s[j]) // 如果字符相同{if (j - i 1){dp[i][j] j - i 1; // 当 j - i 1 时长度为 2 或者 1直接标记回文串长度}else if (dp[i 1][j - 1]) // 当 j - i 1 时查看内部子串是否是回文串{dp[i][j] dp[i 1][j - 1] 2; // 更新回文串长度}}}}// 遍历最后一行找到最大的回文子串长度for (int i n - 1; i 0; i--){if (dp[i][n - 1] max){max dp[i][n - 1];}}cout n - max; // 输出最少需要添加的字符数即字符串长度减去最大回文子串长度}}return 0;
}
