Longest Odd Pallindromes
Problem Description
Given a string S(consisting of only lower case characters) and Q queries.
In each query you will given an integer i and your task is to find the length of longest odd palindromic substring whose middle index is i. Note:
1.) Assume 1 based indexing.
2.) Longest odd palindrome: A palindrome substring whose length is odd.
Problem Constraints
1<=|s|,Q<=1e5
1<=i<=|s|
Input Format
First argument A is string S.
Second argument B is an array of integers where B[i] denotes the query index of ith query.
Output Format
Return an array of integers where ith integer denotes the answer of ith query.

Is there any better way to solve this question other than brute force, that is, when we generate all the palindromic substrings and check

CodePudding user response：

There is Manacher's algorithm that calculates number of palindromes centered at i-th index in linear time.

After precalculation stage you can answer query in O(1). I changed result array to contain lengths of the longest palindromes centered at every position.

Python code (link contains C one)

def manacher_odd(s):
    n = len(s)
    odds = []
    l, r = 0, -1
    for i in range(n):
        k = min(odds[l r-i], r-i 1) if i<=r else 1
        while (i k < n) and (i-k >= 0) and (s[i k]==s[i-k]):
            k  = 1
        odds.append(k)
        if (i k-1 > r):
            l, r = i-k 1, i k-1
    for i in range(n):
       odds[i] = 2 * odds[i] - 1
    return odds

print(manacher_odd("abaaaba"))

[1, 3, 1, 7, 1, 3, 1]

CodePudding user response：

There are 2 possible optimizations they might be looking for.

First, you can do an initial run over S first, cleverly building a lookup table, and then your query will just use that, which I think would be faster if B is long.

Alternatively, if not doing a look up, then while you're searching at index i, you'll potentially search neighboring indexes at the same time. As you check i, you can also be checking i 1, i-1, i 2, i-2, etc... as you go, and save that answer for later. This seems the less promising route to me, so I want to dive into the first idea more.

Finally, if B is quite short, then the best answer might be brute force, actually. It's good to know when to keep it simple.

Initial run method

One optimization that comes to mind for a pre-process run is as follows:

1. Search the next unknown index, brute force it by looking forwards and back, while recording the frequency of each letter (including the middle one.) If a palindrome of 1 or 3 was found, move to the next index and repeat.

2. If a palindrome or 5 or longer was found, calculate mid points of any letters that showed up more than twice which are to the right of the current index.

3. Any point between the current index and the index of the last palindrome letter that isn't in the mid-points list is a 1 for length.

This means you'll search all the midpoints found in (2). After that, you'll continue searching from the index of the last letter of the palindrome found in (2).

An example

Let's say S starts with: ```a, b, c, d, a, f, g, f, g, f, a, d, c, b, a, ...``` and you have checked from ```i = 2``` up to ```i = 7``` but found nothing except a run of 3 at ```i = 7```. Now, you check index ```i = 8```. You will find a palindrome extending out 7 letters in each direction, for a total of 15, but as you check, note any letters that show up more than twice. In this case, there are 3 ```f```s and 4 ```a```s. Find any mid points these pairs have that are right of the current index (8). In this case, 2 ```f```s have a mid point of i=9, the 2 right-most ```a```s have a midpoint of i=13. Once you're done looking at i=8, then you can skip any index not on your list, all the way up to the last letter you found in i=8. For example, we only have to check i=9 and i=13, and then start from i=15, checking every step. We've been able to skip checking i=10, 11, 12, and 14.