Блог пользователя Qualified

Автор Qualified, история, 4 года назад, По-английски

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?

  • Проголосовать: нравится
  • -23
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Your ofc.

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        IDK

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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.

          • »
            »
            »
            »
            »
            »
            4 года назад, # ^ |
            Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

            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.

            • »
              »
              »
              »
              »
              »
              »
              4 года назад, # ^ |
                Проголосовать: нравится -6 Проголосовать: не нравится

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

              • »
                »
                »
                »
                »
                »
                »
                »
                4 года назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится

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

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 года назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится

                  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!

»
4 года назад, # |
Rev. 4   Проголосовать: нравится +19 Проголосовать: не нравится

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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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.