马拉车是什么牌子，马拉车简笔画

?

马拉车算法：在元素向两边扩散进行查找的基本思路不变的情况下，充分利用回文串的对称性，大幅减少算法时间的一种算法（时间复杂度o(n)）。

?

字符的处理

在每个字符和字符串开头与结尾都添加上特殊符号“#”。然后在两端分别加入一个全新的符号，这样可以省去边界的判断。

如”aba“可以改写成”@#a#b#a#$“。

?

几个重要变量的初始化

建立列表p，并给其添加和字符串等数量的0，之后会用来记录每个元素向两边扩散所能达到的最大回文长度。

将max_right，max_mid_index初始化为0，前者用来记录已经观测到的所有回文串中右边界所能到达的最远的地方，后者则是这个回文串的对称点索引值。

?

主体循环

利用索引值进入循环（for i in range(1,len(s) – 1)）。

此时分三种情况：

第一种：

当

i > max_right

时，说明我们没法利用前面已知的数据来判断当前索引值下的元素扩散情况，因此我们让其向两边扩散查找最长回文串即可。查找完后这个回文串的右边界索引值必定大于max_right，故令max_right = i+p[i]-1。相应地，max_mid_index = i

第二种：

当

i max_right: while s[i-p[i]] == s[i+p[i]]: p[i] += 1 max_right = i+p[i]-1 max_mid_index = i else: p[i] = p[2*max_mid_index – i] if p[i] + i – 1 > max_right: p[i] = max_right – i + 1 while s[i-p[i]] == s[i+p[i]]: p[i] += 1 if i + p[i] – 1 > max_right: max_right = i+p[i]-1 max_mid_index = i index = p.index(max(p)) return s[index – p[index] + 1:index + p[index]].replace(\’#\’,\’\’) leetcode 647.回文子串

给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

示例 1：

输入：\”abc\”

输出：3

解释：三个回文子串: \”a\”, \”b\”, \”c\”

示例 2：

输入：\”aaa\”

输出：6

解释：6个回文子串: \”a\”, \”a\”, \”a\”, \”aa\”, \”aa\”, \”aaa\”

?

提示：

输入的字符串长度不会超过 1000 。

class Solution: def countSubstrings(self, s: str) -> int: tem_s = \’@#\’ for i in s: tem_s += i + \’#\’ s = tem_s + \’&\’ Lens = len(s) max_right = 0 max_mid_index = 0 p = [0] * Lens for i in range(1,Lens-1): if i > max_right: while s[i-p[i]] == s[i+p[i]]: p[i] += 1 max_right = i+p[i]-1 max_mid_index = i else: p[i] = p[2*max_mid_index – i] if p[i] + i – 1 > max_right: p[i] = max_right – i + 1 while s[i-p[i]] == s[i+p[i]]: p[i] += 1 if i + p[i] – 1 > max_right: max_right = i+p[i]-1 max_mid_index = i ans = 0 for i in p: ans += int(i/2) return ans

?

《马拉车是什么牌子，马拉车简笔画》来自互联网同行内容，若有侵权，请联系我们删除！