text: # 最长连续回文串Swift实现
  
  ## 题目：Longest Palindromic Substring
  
  Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
  
  Example:
  
  ``````Input: "babad"
  
  Output: "bab"
  
  Note: "aba" is also a valid answer.
  ``````
  
  Example:
  
  ``````Input: "cbbd"
  
  Output: "bb"
  ``````
  
  ## 算法分析
  
  ### 解法二：
  
  • 动态规划，时间复杂度:O(n^2)。
  dp[i][j] 表示从i~j的子串是否是回文串。
  
  ``````dp[i][j] = {
  dp[i-1][j + 1] : s[i] == s[j],
  false          : s[i] != s[j]
  }
  ``````
  
  Swift实现
  
  ``````class Solution {
  func longestPalindrome(_ s: String) -> String {
  var dp:[[Bool]] = [];
  if s.count <= 1{
  return s;
  }
  
  var longest:Int = 1;
  var left:Int = 0;
  var right:Int = 0;
  
  for var i in 0...s.count - 1{
  var eachRow:[Bool] = [];
  for var j in 0...s.count - 1{
  if i == j{
  eachRow.append(true);
  }else{
  eachRow.append(false);
  }
  }
  dp.append(eachRow);
  }
  
  var i:Int = 0;
  var j:Int = 0;
  for var character_j in s {
  if j == 0 {
  j += 1;
  continue;
  }
  i = 0;
  for var character_i in s {
  if character_i == character_j {
  dp[i][j] = dp[i + 1][j - 1] || j - i <= 1;
  if dp[i][j] && j - i + 1 > longest{
  longest = j - i + 1;
  left = i;
  right = j;
  }
  }else{
  dp[i][j] = false;
  }
  i += 1;
  if i >= j{
  break;
  }
  }
  j += 1;
  }
  let leftIndex = s.index(s.startIndex, offsetBy: left);
  let rightIndex = s.index(s.startIndex, offsetBy: right);
  return String(s[leftIndex...rightIndex]);
  }
  }
  ``````
  
  AC结果：可能是swift处理字符串的效率问题会超时。
  
  ``````Time Limit Exceeded
  ``````
  
  ### 第三种解法
  
  • Manacher算法,时间复杂度：O(n)。
  
  Manacher's ALGORITHM: O(n)时间求字符串的最长回文子串思路分析这里介绍的很清晰，
  
  #### 首先解决回文长度为奇偶的问题
  
  • 插桩处理，整个字符串的前后间隔处插入'#'字符，最终得到的字符串就一定是奇数长度，回文的长度也一定是奇数长度。
  
  ``````# c # b # b # d #
  1 2 1 2 3 2 1 2 1
  ``````
  
  #### 解决计算`P[i]`问题
  
  Longest Palindromic Substring_1.png
  
  Longest Palindromic Substring_2.png
  
  ``````//记j = 2 * id - i，也就是说 j 是 i 关于 id 的对称点(j = id - (i - id))
  P[i] = {
  P[j] ,mx - i > P[j]
  mx - i, mx - i <= P[j]
  }
  ``````
  
  #### Swift 实现
  
  ``````class Solution {
  func longestPalindrome(_ s: String) -> String {
  if s.count <= 1 {
  return s;
  }
  
  // 1.间隔之间先插入#
  var newString:String = "#";
  for var character in s {
  newString.append(character);
  newString = newString + "#";
  }
  let characters = Array(newString);
  
  // 2.遍历找出以每个节点作为轴最长半径
  var maxId:Int = 0;
  var max:Int = 0;
  var ids:[Int] = [];
  ids.append(1);
  var maxLength:Int = 1;
  var maxLengthIndex = 0;
  
  for var i in 1...characters.count - 1 {
  var j:Int = maxId - (i - maxId);
  if max > i && j >= 0 {
  ids.append(min(ids[j], max - i));
  }else{
  ids.append(1);
  }
  while i + ids[i] <= characters.count - 1 && i - ids[i] >= 0 && characters[i + ids[i]] == characters[i - ids[i]]{
  ids[i] += 1;
  }
  
  if i + ids[i] - 1 > max {
  maxId = i;
  max = i + ids[i] - 1;
  }
  
  if ids[i] > maxLength{
  maxLength = ids[i];
  maxLengthIndex = i;
  }
  }
  let leftIndex = s.index(s.startIndex, offsetBy: (maxLengthIndex - (maxLength - 1))/2);
  let rightIndex = s.index(leftIndex, offsetBy:maxLength - 1 - 1);
  return String(s[leftIndex...rightIndex]);
  }
  }
  ``````
  
  AC结果：
  
  ``````Accepted
  ``````