/**
 * @param {string} s
 * @return {number}
 */
const countSubstrings1 = function (s) {
  let res = 0;
  for (let i = 0, ii = s.length; i < ii; ++i) {
    let j = 1, temp = 1;
    if (s[i] === s[i + 1]) {
      ++temp;
      while (s[i - j] === s[i + j + 1] && i - j >= 0 && i + j + 1 < ii) {
        ++j;
        ++temp;
      }
    }
    j = 1;
    while (s[i - j] === s[i + j] && i - j >= 0 && i + j < ii) {
      ++j;
      ++temp;
    }
    res += temp;
  }
  console.log(res);
};
const countSubstrings = function (s) {
  let Mp = [], Ma = [], slen = s.length;
  Ma.push('$');
  for (let i = 0; i < slen; ++i) {
    Ma.push('#', s[i]);
  }
  Ma.push('#');
  Ma.push('*')
  console.log(Ma,Mp);
  console.log(s.length, Ma.length);
  let mx = 0, id = 0;
  // return
  for (let i = 1; i < (2 * slen + 1); ++i) { // i代表了当前正在判断Ma串的第i位为中心的回文子串最长长度。
    Mp[i] = mx > i ? Math.min(Mp[2 * id - i], mx - i) : 1 // 核心代码
    while (Ma[i + Mp[i]] === Ma[i - Mp[i]]) {
      ++Mp[i];
    }
    if (mx < i + Mp[i]) {
      mx = i + Mp[i];
      id = i;
    }
  }
  console.log(Mp);
}

// Manacher版本
const countSubstrings = function (s) {
  let Mp = [], Ma = [], slen = s.length, res = 0;
  Ma.push('$');
  for (let i = 0; i < slen; ++i) {
    Ma.push('#', s[i]);
  }
  Ma.push('#');
  Ma.push('*')
  console.log(Ma, Mp);
  console.log(s.length, Ma.length);
  let mx = 0, id = 0;
  // return
  for (let i = 1; i < (2 * slen + 1); ++i) { // i代表了当前正在判断Ma串的第i位为中心的回文子串最长长度。
    Mp[i] = mx > i ? Math.min(Mp[2 * id - i], mx - i) : 1 // 核心代码
    while (Ma[i + Mp[i]] === Ma[i - Mp[i]]) {
      ++Mp[i];
    }
    if (mx < i + Mp[i]) {
      mx = i + Mp[i];
      id = i;
    }
  }
  for (let i = 2; i < (2 * slen + 1); ++i) {
    if ((i & 1) === 1) { // 奇数
      if (Mp[i] > 1) {
        res += ((Mp[i] - 1) / 2)
      }
    } else {
      if (Mp[i] > 2) {
        res += (Mp[i] / 2)
      } else {
        ++res;
      }
    }
  }
  console.log(res);
}