Program to find length of longest chunked palindrome decomposition in Python

Suppose we have a text. We have to find the largest possible k such that there exists a[1], a[2], ..., a[k] such that: Each a[i] is a string which is not blank. And their concatenation a[1] + a[2] + ... + a[k] is equal to the given text; For all i in range 1 to k, a[i] = a[{k+1 - i}].

So, if the input is like text = "antaprezatepzapreanta", then the output will be 11 because we can split it like "a|nt|a|pre|za|tpe|za|pre|a|nt|a".

To solve this, we will follow these steps −

• counter := 0

• i := 1, j := size of text - 1

• ic := 0, jc := size of text

• while i <= j, do

  • if substring of text[from index ic to i-1] is same as substring of text[from index j to jc-1], then

    • counter := counter + 2

    • ic := i

    • jc := j

  • i := i + 1

  • j := j - 1

• if ic is not same as jc, then

  • counter := counter + 1

• return counter

Example

Let us see the following implementation to get better understanding

def solve(text):    counter = 0    i, j = 1, len(text) - 1    ic, jc = 0, len(text)    while i <= j:       if text[ic:i] == text[j:jc]:          counter += 2          ic = i          jc = j       i += 1       j -= 1 if ic != jc: counter += 1 return counter text = "antaprezatepzapreanta" print(solve(text))

Input

[3,4,5,2,1,7,3,4,7], 3 

Output

11