My solution is using Manacher algorithm. Time is 3ms. Not the fastest.

The Manacher is O(N) time complexity, so is this algorithm O(N)? I would appreciate it a lot if someone can figure it out.

```
class Solution {
public:
int countSubstrings(string s) {
ostringstream os;
os<<"#";
for(char c : s) {
os<<c<<"#";
}
string ns = os.str();
int n = ns.length();
int *rl = new int[n];
int id = 0, mx = 0;
for(int i = 0; i < n; i++) {
if(i < mx) rl[i] = min(rl[2 * id - i], mx - i);
else rl[i] = 1;
//尝试扩展
while(i - rl[i] >= 0 && i + rl[i] <= n - 1 && ns[i - rl[i]] == ns[i + rl[i]]) rl[i]++;
if(i + rl[i] > mx) {
mx = i + rl[i];
id = i;
}
}
int ret = 0;
for(int i = 0; i < n; i++) {
ret += rl[i] / 2;
}
delete[] rl;
return ret;
}
};
```