Bijection between binary strings with an even-length palindromic prefix and binary strings with a bifix

Question

As Danny Rorabaugh's OEIS sequence A262312 suggests, the number of binary words of length $n$ that begin with a even-length palindromic prefix is the same as the number of binary words of length $n$ that have a matching prefix and suffix (sometimes called a "bifix").

I'm interested in finding a bijection $$ \phi_n\colon \big\{s \in \{0,1\}^n : s \text{ has an even-length palindromic prefix}\big\} \rightarrow \big\{s \in \{0,1\}^n : s \text{ has a bifix}\big\} $$ between these sets such that the length of the longest palindromic prefix of $s$ is equal to the total length of the longest bifix of $\phi_n(s)$.

For instance, a map $\underline{1001}1 \mapsto \underline{01}1\underline{01}$ is good, because the palindromic prefix on the left has length four, which is equal to the (total) length of the bifix on the right. However, the map $\underline{00}010 \mapsto \underline{00}1\underline{00}$ is not acceptable, because the palindromic prefix on the left has length two, but the (total) length of the bifix on the right has length four.

Is there a natural way to create a length-preserving bijection like this?

Answer 1

The bijection is discussed in my paper with Daniel Gabric, Borders, palindrome prefixes, and square prefixes, Information Processing Letters, 165 (2021), 106027. See https://doi.org/10.1016/j.ipl.2020.106027 .

Answer 2

The map that Jeffrey Shallit refererences in his paper with Daniel Gabric ("Borders, palindrome prefixes, and square prefixes") is based on a "perfect shuffling map". For a given word $a_1 a_2 \dots a_n$ with a "short" bifix of length $k$, the map$$ f(a_1 a_2 \dots a_n) = \begin{cases} a_1a_na_2a_{n-1}\dots a_{\frac{n-1}{2}}a_\frac{n+3}{2}a_{\frac{n+1}{2}}, & n \text{ is odd}; \\ a_1a_na_2a_{n-1}\dots a_{\frac{n}{2}}a_{\frac{n+2}{2}}, & n \text{ is even}.\\ \end{cases} $$

results in a word with an initial palindrome of order $k$ (length $2k$).