Qualified's blog

Finding the borders of all palindromic substrings
By Qualified, history, 4 years ago, In English

I know that using Manacher's algorithm, we can find all pairs ($$$i$$$, $$$j$$$) such that s[i $$$\dots$$$ j] is a palindrome. This article on cp-algorithms uses 2 vectors, one in which the $$$i$$$ is the center of an odd length palindrome, the other in which the $$$i$$$ is the latter of the 2 middle elements of an even length palindrome. But how do we convert this information into a vector<pair<int, int>> where the pair represents the boundaries of the palindrome substring?

  • Vote: I like it
  • -23
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Are you sure that is solvable in O(N)?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Which is solvable in $$$O(n)$$$? Manacher's algo or my question?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Your ofc.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        IDK

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I don't think you can solve in O(N). The best I can tell you is O(N^2) solution, where you fix the ends of the substring and check in O(1) is it palindrome or not. I would use hashing to check since I'm not aware of any other string techniques.

          BTW It is very interesting whether O(N) solution exists or not.

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
            ← Rev. 2   Vote: I like it 0 Vote: I do not like it

            How would you use hashing to figure out if a substring is a palindrome? Also, how would you get a substring of a string given the endpoints in $$$O(1)$$$. String.substr method is linear.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              4 years ago, # ^ |
                Vote: I like it -6 Vote: I do not like it

              I think you don't understand hashing. You pre-calculate stuff and then check in O(1).

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                4 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                But how would you get the substring of a string in $$$O(1)$$$?

                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  You don't need the substring itself to get a hash of that substring, because you have pre-calculated things already. Well, if you have still doubts, check out some hashing tutorial!

                  → Reply
»
4 years ago, # |
← Rev. 4   Vote: I like it +19 Vote: I do not like it

If you have a palindromic string, the string will stay palindrome after popping a character from the front and from the back.

You can use this to get that vector you want from the Mancher vectors. Mancher vector has info about the largest subpalindrome centered at $$$i$$$. If that subpalindrome is $$$s[l .. r]$$$ then $$$s[l + k .. r - k]$$$ is also a palindrome for all $$$k$$$, $$$l + k \leq r - k$$$ (Imagine popping $$$k$$$ characters from the front and from the back). You can bruteforce this to get your desired vector but be careful that its size will be $$$O(n^2)$$$.

There are other info that can be calculated in $$$O(n)$$$ that you may probably find useful instead of that $$$n^2$$$ sized borders vector you're looking for.
Here is some code that calculates how many subpalindromes start, finish, or cover index $$$i$$$: https://ideone.com/d77lMo If you're interested in this, I can provide an explanation for what the code is doing.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Is there a way to get the boundaries of all substrings that are palindromes of a string in $$$O(n^{2})$$$ or less?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I've already told you O(n^2) approach.

      The less is impossible since you can have as much as (n+1)*n/2 substrings in total (when all the characters are same). How could you construct the vector with let's say n^2 values in less than n^2 time? It's impossible.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Having the implementation would be helpful. I haven't learned string hashing yet but it is on my TODO list.

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          It's like prefix sums where you find the sum of some segments in O(1) without checking the values. The approach is same for getting the substring hash, you don't need to check the characters itself.

          So if you need L..R substring hash almost like in prefix sums you take R prefix and remove L — 1 prefix from it. There is an easy formula for it.

          → Reply