ABC468D
495 字
2 分钟
ABC468D
题目描述
思路
对于一个字符串,若想要判断该字符串的子串是否回文,则需要明确一个中心和一个半径.
因此,对于此题,我们枚举中心,并向两边扩展(加长半径),对于扩展的一对字符,若这两个字符不相同,则将 diff 增加 1,若 diff 增加到 2,则剪枝,并更换中点.
标程:
#include <bits/stdc++.h>using namespace std;string s;int ans;signed main() { cin >> s; for (int i = 0; i < s.size(); i++) { // 奇数:中点为 i int diff = 0; for (int r = 0; i - r >= 0 && i + r < s.size(); r++) { // 半径为 r(仅存在i则半径为0) if (s[i - r] != s[i + r]) diff++; if (diff >= 2) { break; } ans++; } } for (int i = 0; i < s.size() - 1; i++) { // 偶数:中点为 i 和 i+1 之间 int diff = 0; for (int r = 0; i - r >= 0 && i + r + 1 < s.size(); r++) { // 半径为 r(仅存在i和i+1则半径为0) if (s[i - r] != s[i + r + 1]) diff++; if (diff >= 2) { break; } ans++; } } cout << ans;}这样的算法时间复杂度 .勉强可以通过.
这道题还可以使用哈希 + 二分的方法,在这里不再赘述.
文章分享
如果这篇文章对你有帮助,欢迎分享给更多人!


