Palindromic Substrings

Question: 647. Palindromic Substrings

Given a string s, return the number of palindromic substrings in it. A string is a palindrome when it reads the same backward as forward. A substring is a contiguous sequence of characters within the string.

Code

class Solution {
public:
    string stringToOddPalindromeFormat(string s){
        std::string result = "@";
        for(char c : s) {
            result += "#";
            result += c;
        }
        result += "#$";
        return result;
    }

    int countSubstrings(string s) {
        std::string str = stringToOddPalindromeFormat(s);
        int str_size = str.size();
        std::vector<int> p(str_size,0);
        int center = 0, right = 0, result = 0;

        for(int i=1; i<str_size-1; i++){
            int mirror = 2*center-i;

            if(i<right){
                p[i] = min(right-i, p[mirror]);
            }
            while(str[i+(1+p[i])] == str[i-(1+p[i])]){
                p[i]++;
            }
            if(i+p[i]>right){
                center = i;
                right = i+p[i];
            }
            result += (p[i] + 1)/2;
        }

        return result;
    }
};