manacher算法

public char[] manacherString(String str) {
  char[] charArr = str.toCharArray();
  char[] res = new char[str.length() * 2 + 1];
  int index = 0;
  for (int i = 0; i != res.length; i++) {
    res[i] = (i & 1) == 0 ? '#' : charArr[index++];
  }
  return res;
}

public int (String str) {
  if (str == null || str.length() == 0) {
    return 0;
  }
  char[] charArr = manacherString(str);
  int[] pArr = new int[charArr.length]; 
  int index = -1; // 回文中心位置
  int pR = -1; // 回文半径即将到达的下一个位置
  int max = Integer.MIN_VALUE;
  
  for (int i = 0; i != charArr.length; i++) {
    
    // pArr[2*index-i]:与i对应位置j的回文半径长度
    // pR-i:i到边界值pR的距离
    pArr[i] = pR > i ? Math.min(pArr[2 * index - i], pR - i) : 1;
    
    while (i + pArr[i] < charArr.length && i - pArr[i] > -1) {
      if (charArr[i + pArr[i]] == charArr[i - pArr[i]])
        pArr[i]++;
      else {
        break;
      }
    }
    
    if (i + pArr[i] > pR) {
      pR = i + pArr[i];
      index = i;
    }
    
    max = Math.max(max, pArr[i]);
  }
  
  return max - 1;
}