/**
* @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);
}