title: How the initial palindrome length at index i equal to R - i in "Manacher's algorithm"?
body: <p>I am learning the Manacher's algorithm to solve the Longest Palindromic Substring problem and I understand that it leverages the fact that if i' is centre of palindrome then there will be a palindrome centred at i. </p>
  
  <p>Instead of expanding from zero , we maintain a array P to keep track of len of palindromes centre at i as we go.
  My question is how do we know the there will be palindrome of size R-i if palindrom at mirror is smaller?</p>
  
  <p>This is the code for it.</p>
  
  <pre class="lang-py prettyprint-override"><code>    def longestPalindrome(self, s):
          # Transform S into T.
          # For example, S = "abba", T = "^#a#b#b#a#$".
          # ^ and $ signs are sentinels appended to each end to avoid bounds checking
          T = '#'.join('^{}$'.format(s))
          n = len(T)
          P = [0] * n
          C = R = 0
          for i in range (1, n-1):
  
              if (R &gt; i):
                 # WHY R-i, how do we know there will be palindrome of size R -i
                  P[i] =  min(R - i, P[2*C - i]) 
  
              # Attempt to expand palindrome centered at i
              while T[i + 1 + P[i]] == T[i - 1 - P[i]]:
                  P[i] += 1
  
              # If palindrome centered at i expand past R,
              # adjust center based on expanded palindrome.
              if i + P[i] &gt; R:
                  C, R = i, i + P[i]
  
          # Find the maximum element in P.
          maxLen, centerIndex = max((n, i) for i, n in enumerate(P))    
          return s[(centerIndex  - maxLen)//2: (centerIndex  + maxLen)//2]
  </code></pre>
  
  <p>all the example that that I found are like </p>
  
  <pre><code>a # b # a # b # b # a # b # a
     i'          C         i    
  </code></pre>
  
  <p>I understand that in this case there are subpalindromes at i, but what about cases like </p>
  
  <pre><code>a # b # c # d # d # c # b # a
     i'          C         i    
  </code></pre>
  
  <p>How do we know P[i] will either be R-i or Palindrome at mirror ?</p>