最长回文串_回文三板斧(第三招：挖掘马拉车的剩余价值)

有些题目需要频繁的判断任意子串是否是回文的。本文分享一下利用马拉车的长度数组判断任意子串是否回文的方法&＃xff0c;时间复杂度低至 O(1) 。

先来回忆一下马拉车&＃xff1a;

• 选择占位符&＃xff0c;根据原始字符串 S 构造字符串 PS。
• 以 O(n) 的时间复杂度计算长度数组 len。len[i] 表示 PS 中&＃xff0c;以 PS[i]为中心的最长的回文子串的长度。

当我们要判断 S[L:R]是否为回文串时&＃xff0c;仅需两个步骤&＃xff1a;

• 找到 PS 中与 S[L:R] 对应的子串位置&＃xff0c;记为 PS[L&＃39;: R&＃39;]。
  • L&＃39; &＃61; L*2&＃43;1&＃xff1b;R&＃39; &＃61; R*2&＃43;1
• 判断 len[mid] 是否小于PS[L&＃39;:R&＃39;]的长度。如果小于&＃xff0c;则S[L:R]不是回文&＃xff0c;反之则是。
  • mid &＃61; (L&＃39; &＃43; R&＃39;) / 2

以 S[1:5] 为例&＃xff0c;首选换算对应子串位置&＃xff0c;得到 PS[3:11]&＃xff0c;找到PS[3:11]的中心 PS[7]&＃xff0c;通过查询长度数组 len&＃xff0c;得知以 PS[7] 为中心的最长回文串的长度为 15。显然 PS[3:11] 及 S[1:5] 都是回文的。偶数长度的字符串同样有效&＃xff0c;比如 S[6:7]&＃xff0c;老铁们可自行验证~

░尝试证明一下

因为 len[mid] 记录的是以 PS[mid] 为中心的最长回文子串的长度。而S[L:R] 对应的PS[L&＃39;:R&＃39;]也是以 PS[mid] 为中心的子串。显然&＃xff1a;

• 当 PS[L&＃39;:R&＃39;] 的长度不超过 len[i] 时&＃xff0c;PS[L&＃39;:R&＃39;] 一定是回文串。
• 当 PS[L&＃39;:R&＃39;] 超过 len[mid]&＃xff0c;PS[L&＃39; : R&＃39;] 一定不是回文串。

否则的话就与长度数组 len 的定义矛盾了&＃xff0c;所以上述结论一定是成立的。

░几个练习题

• 5. 最长回文子串
• 647. 回文子串
• 131. 分割回文串
• 132. 分割回文串 II

吐了&＃xff0c;公众号不能添加链接&＃xff0c;老铁们可以在 Leetcode 上自行搜索&＃xff0c;可以从"阅读原文"中跳转~