题解：AtCoder AT_abc468_d Pre-Palindrome

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】AtCoderPre-Palindrome【题目描述】A string consisting of lowercase English letters is called agood stringif it satisfies the following condition.It can be turned into a palindrome by rewriting at most one character.For example,a,iwai, andabcdczaare good strings, butabcdandatcoderare not good strings. Note that, in particular, a palindrome is also a good string.You are given a stringS SSconsisting of lowercase English letters.Find the number of non-empty substrings (contiguous subsequences) ofS SSthat are good strings.Two substrings taken from different positions ofS SSare counted separately even if they are equal as strings.What is a substring?AsubstringofS SSis a string obtained by deleting zero or more characters from the beginning and zero or more characters from the end ofS SS.For example,abis a substring ofabc, butacis not a substring ofabc.由小写英文字母组成的字符串如果满足以下条件则称为好字符串。通过重写最多一个字符它可以变成一个回文串。例如a、iwai和abcdcza是好字符串但abcd和atcoder不是好字符串。注意特别地回文串本身也是好字符串。给定一个由小写英文字母组成的字符串S SS。求S SS中是好字符串的非空子串连续子序列的数量。即使两个子串作为字符串相等只要它们取自S SS的不同位置就分别计数。什么是子串S SS的子串是指从S SS的开头删除零个或多个字符、并从末尾删除零个或多个字符后得到的字符串。例如ab是abc的子串但ac不是abc的子串。【输入】The input is given from Standard Input in the following format:S SS【输出】Output the answer.【输入样例】ababa【输出样例】13【核心思想】问题分析给定字符串S SS求其中有多少个非空子串是好字符串——即通过修改最多一个字符可以变成回文串。回文串本身也是好字符串。这是一个双指针扩展 回文判定问题核心在于利用回文的对称性从中心向两边扩展并统计不匹配字符数。算法选择中心扩展法枚举每个可能的回文中心奇数长度为中心字符偶数长度为中心缝隙向两边扩展并统计不匹配数提前终止不匹配数超过1 11时立即停止扩展关键步骤读入数据读取字符串S SS长度n nn奇数长度子串中心m i d midmid从0 00到n − 1 n-1n−1l r m i d l r midlrmidm i s 0 mis 0mis0a n s ← a n s 1 ans \leftarrow ans 1ans←ans1长度为1 11总是好字符串向两边扩展l 0 l 0l0且r n − 1 r n-1rn−1l ← l − 1 l \leftarrow l - 1l←l−1r ← r 1 r \leftarrow r 1r←r1m i s ← m i s [ s [ l ] ≠ s [ r ] ] mis \leftarrow mis [s[l] \neq s[r]]mis←mis[s[l]s[r]]若m i s ≤ 1 mis \leq 1mis≤1a n s ← a n s 1 ans \leftarrow ans 1ans←ans1否则b r e a k breakbreak偶数长度子串中心缝隙m i d midmid从0 00到n − 2 n-2n−2l m i d l midlmidr m i d 1 r mid 1rmid1m i s [ s [ l ] ≠ s [ r ] ] mis [s[l] \neq s[r]]mis[s[l]s[r]]若m i s ≤ 1 mis \leq 1mis≤1a n s ← a n s 1 ans \leftarrow ans 1ans←ans1然后向两边扩展同奇数情况输出结果a n s ansans时间/空间复杂度时间复杂度O ( n 2 ) O(n^2)O(n2)最坏情况每个中心扩展O ( n ) O(n)O(n)共2 n 2n2n个中心空间复杂度O ( 1 ) O(1)O(1)仅使用指针和计数器中心扩展与提前终止的核心思想回文的对称性从中心向两边扩展时新加入的字符对( s [ l ] , s [ r ] ) (s[l], s[r])(s[l],s[r])若相同则不影响回文性若不同则增加一次修改需求修改次数的单调性向两边扩展只会增加或保持不匹配数不会减少。因此一旦m i s 1 mis 1mis1后续扩展必然不满足条件可直接终止两种中心类型奇数长度子串有n nn个中心点偶数长度子串有n − 1 n-1n−1个中心缝隙覆盖所有可能的子串计数策略每个满足m i s ≤ 1 mis \leq 1mis≤1的扩展状态对应一个好字符串子串直接累加。由于不同位置的相同子串分别计数无需去重适用于回文相关子串统计、中心扩展类字符串问题【算法标签】#模拟【代码详解】#includebits/stdc.husingnamespacestd;#defineintlonglong// 将int定义为long long避免子串数量过多导致溢出string s;// 输入的字符串Sintans;// ans记录好字符串子串的总数signedmain()// 使用signed main配合#define int long long{cins;// 读入字符串Sintns.size();// n为字符串S的长度// 第一步枚举奇数长度子串的中心点中心为单个字符for(intmid0;midn;mid)// 遍历每个可能的中心位置{intlmid,rmid;// 初始化左右指针都指向中心点形成长度为1的子串intmis0;// mis记录当前子串中不匹配的对称位置对数即需要修改的字符数ans;// 长度为1的子串总是回文串0次修改一定是好字符串直接计数while(l0rn-1)// 向两边扩展确保不越界{l--;// 左指针向左移动r;// 右指针向右移动mis(s[l]!s[r]);// 如果新扩展的两端字符不同不匹配数加1if(mis1)// 如果不匹配数不超过1最多修改1个字符可变成回文ans;// 该子串是好字符串计数加1else// 如果不匹配数超过1break;// 继续扩展只会增加不匹配数直接退出}}// 第二步枚举偶数长度子串的中心点中心为两个相邻字符之间for(intmid0;midn-1;mid)// 遍历每对相邻字符作为中心{intlmid,rmid1;// 初始化左右指针指向相邻的两个字符形成长度为2的子串intmis(s[l]!s[r]);// 初始不匹配数为中间两个字符是否相同0或1if(mis1)// 如果长度为2的子串最多需要修改1个字符{ans;// 该长度为2的子串是好字符串计数加1while(l0rn-1)// 向两边扩展确保不越界{l--;// 左指针向左移动r;// 右指针向右移动mis(s[l]!s[r]);// 如果新扩展的两端字符不同不匹配数加1if(mis1)// 如果不匹配数不超过1ans;// 该子串是好字符串计数加1else// 如果不匹配数超过1break;// 继续扩展只会增加不匹配数直接退出}}}coutansendl;// 输出好字符串子串的总数return0;}【运行结果】ababa 13