Leetcode 1147. Longest Chunked Palindrome Decomposition - Rolling hash O(n) Solution

key concept:

1. " (factor*(a mod b)) mod b "  equl  " (factor*a) mod b "
2. " (factor*a + b) mod c " equl " (factor*(a mod c) + b ) mod c"

 <pre><code class='html'>

class Solution

{

public:

    int longestDecomposition(string text)

    {

        auto myHash = [](char ch)

        {

            return hash<char>{}(ch);

        };

        if (text.size() == 1)

            return 1;

        int left = 0;

        int right = text.size() - 1;

        int len = 1;

        int ans = 0;

        size_t lHash = 0;

        size_t rHash = 0;

        int prime = 1e9 + 7;

        while (left < right)

        {

            lHash *= 26;

            lHash += myHash(text[left]);

            lHash %= prime;

            // rHash += myHash(text[right]) *static_cast<int>(pow(26,(len - 1)));

            if (true)

            {

                size_t temp = myHash(text[right]);

                for (int i = 0; i < len - 1; i++)

                {

                    temp *= 26;

                    temp %= prime;

                }

                rHash += temp;

            }

            rHash %= prime;

            if (lHash == rHash)

            {

                ans += 2;

                len = 1;

                lHash = 0;

                rHash = 0;

            }

            else

                len++;

            left++;

            right--;

        }

        if (left == right || len > 1)

            ans += 1;

        return ans;

    }

};

</code></pre>