Find the index of reflection of a substring of a palindrome [closed]

Question

Problem Statement: You will receive a substring of a palindromic string. You must return the index of the substring which marks the point of reflection of the original string. You are only provided the substring, which is not necessarily a palindrome because it is not necessarily centered about the middle of the original palindromic string.

Input: Substring of length 2n + 1, 1 <= n <= 1000, which encompasses the center of reflection of some larger palindromic string.

Output: Return the index of the substring which marks the point of reflection. May be 0-indexed or 1-indexed.

Test cases (character at desired index is bold to show the desired output more clearly):

Input

1. manaplanacanalpan
2. caroracati
3. wlatemymeta
4. nasanita

Output

1. 9 (the full string was “a man a plan a canal panama”, with spaces removed)
2. 4 (the full string was “was it a car or a cat i saw”, with spaces removed)
3. 6 (the full string was “mr owl are my metal worm”, with spaces removed)
4. 2 (the full string was “oozy rat in a sanitary zoo”, with spaces removed)

Winning Criterion: This is code-golf Shortest code in bytes wins.

Assumption: Assume there is just a single candidate palindrome

Restriction:0 and 2n (last index) are invalid output.

Answer 1

J, ²⁶ 25 bytes

[:(-:@i.>./)[:(*/*#)/.=/~

Try it online!

how

=/~ creates a function table comparing all possible pairs of characters. Taking 'nasanita' as an example:

1 0 0 0 1 0 0 0
0 1 0 1 0 0 0 1
0 0 1 0 0 0 0 0
0 1 0 1 0 0 0 1
1 0 0 0 1 0 0 0
0 0 0 0 0 1 0 0
0 0 0 0 0 0 1 0
0 1 0 1 0 0 0 1

Notice the /-direction diagonals. If one of those is all ones, it corresponds to an embedded palindrome.

J has an adverb /. which lets us to apply a verb to each diagonal.

We choose the verb (*/*#) -- the sum multiplied by the length. Thus it will be the length of the diagonal if it's all ones, and 0 otherwise:

1 0 0 0 5 0 0 0 0 0 0 0 0 0 1

i.>./ Find the index of the max element within that list. In this case the index of 5 is 4.

-:@ And divide it by 2.

Answer 2

Python 2, 65 bytes

f=lambda s,n=1:n*(s[n+1:2*n+1]==s[n-1:n-len(s)<<1:-1])or f(s,n+1)

Try it online!

---

Consider the string abcdefg. Here's what it looks like checking for palindromes around each character:

abcdefg
a c
ab de
abc efg
  cd fg
    e g

We see for the right string, the index goes from n+1 to 2*n+1. The left string is trickier, but looking in reverse (starting from the end of the string) we start at n-1 and move to 2*(n-len(s)) (this is a negative number that indexes from the back of the string). Since we can assume there is only one viable palindrome candidate, we can terminate early if we find one.

---

Python 3.8, 72 bytes

f=lambda s,t='':(max(k:=s[1:],t).find(min(k,t))==0)*len(t)or f(k,s[0]+t)

Try it online!

This approach seemed promising but was just longer.

Answer 3

Retina, 53 bytes

Lv$`((.)+).(?<-2>\2)+(?(2)(?!))
$.1;$.($`$1
N`
L`\d+$

Try it online! Link includes test cases. 0-indexed. Explanation:

((.)+).(?<-2>\2)+(?(2)(?!))

Match and separately capture a number of characters in \2, then match the centre character, then match and pop each character from \2, ensuring that all matched characters get popped. This therefore ensures that the whole match is a palindrome.

Lv$`
$.1;$.($`$1

Consider all overlapping matches and output the length of the palindromic prefix and position of the centre (which is the position of the match plus the length of the palindromic prefix).

N`

Sort in order of length.

L`\d+$

Take the position of the last (i.e. longest) match.

Answer 4

Raku, 47 40 bytes

{m:ex/.+)>.<{$/.flip}>/.max(*.chars).to}

Try it online!

Match all palindromes in the string, find the maximum length one, and output its center index.