Given two strings ~S,S'~, we let ~SS'~ denote their concatenation, and ~\overline{S}~ denote the string that results from reversing ~S~.

Suppose ~(a,b,c)~ is a palindromic triple. Write ~S = S_aS_bS_c~. We have three cases:

• Case 1: ~S_b~ contains the midpoint of ~S~. We again have three cases:

  • Case 1a: ~S_b = PA~, where ~P~ is an odd length palindrome and ~A\neq\varepsilon~ is not the empty string.

    Then for ~S~ be be a palindrome, we must have ~S_a = \overline{S_c}\overline{A}~.

  • Case 1b: ~S_b = P~, where ~P~ is an odd length palindrome.

    Then for ~S~ be be a palindrome, we must have ~S_a = \overline{S_c}~.

  • Case 1c: ~S_b = AP~, where ~P~ is an odd length palindrome and ~A\neq\varepsilon~ is not the empty string.

    Then for ~S~ be be a palindrome, we must have ~S_c = \overline{A}\overline{S_a}~. \end{itemize}

• Case 2: ~S_a~ contains the midpoint of ~S~. We can write ~S_a = AP~, where ~P~ is an odd length palindrome. We need ~S_bS_c = \overline{A}~.

• Case 3: ~S_c~ contains the midpoint of ~S~. We can write ~S_a = PA~, where ~P~ is an odd length palindrome. We need ~S_aS_b = \overline{A}~.

It is clear these cases are disjoint, and it can be checked that they are exhaustive.

To count the number of palindromic triples satisfying Case 1a, we need to count the number of pairs ~(S_a, S_c)~ such that ~S_a = \overline{S_c}\overline{A}~. To do so, we will precompute $$\displaystyle \mathit{cnt}_1[A] = \#\{(i,j) : S_i = \overline{S_j}\overline{A}\}.$$ To build this table, for each ~S_i~, we can consider all ~|S_i|-1~ ways to write ~S_i~ as a prefix and a suffix ~S_i = B\overline{A}~; then the number of pairs ~S_i~ contributes to ~\mathit{cnt}_1[A]~ is precisely the number of strings ~S_j~ such that ~S_j = \overline{B}~. This can be computed in ~O(1)~ time by computing rolling hashes for all strings ~S_i~ and ~\overline{S_i}~. Thus the pre-computation takes time ~O\left(\sum_i |S_i|\right) = O(\ell)~.

Case 1c is similar, but instead we precompute $$\displaystyle \mathit{cnt}_2[A] = \#\{(i,j) : S_i = \overline{A}\overline{S_j}\}.$$ which can be done similarly to the previous case.

For Case 1b, we need to compute the number of pairs of strings ~(S_i,S_j)~ where ~S_i = \overline{S_j}~; this can be done in ~O(N)~ time by using our precomputed hashes.

To count the number of palindromic triples satisfying Case 2, we want to find all pairs ~(S_i,S_j)~ such that ~S_iS_j = \overline{A}~.

To do this naïvely, we would try all ~|A|~ ways to split ~A~ into a prefix and suffix ~A = A_1A_2~ and check if there exists ~S_i = \overline{A_2}~ and ~S_j = \overline{A_1}~ via our hashes. By a classical application of square root decomposition, we know there are at most ~O(\sqrt{\ell})~ possible lengths for ~S_i~, so we only have to check ~O(\sqrt{\ell})~ splits. Case 3 is similar to Case 2, but mirrored.

Finally, the preprocessing for all the cases can be done in ~O(\ell)~ time. As the string ~S_i~ has ~O(|S_i|)~ possible midpoints to check, and the cases can be checked in ~O(\sqrt{\ell})~, the final time complexity is $$\displaystyle O\left(\sum_i |S_i|\sqrt{\ell}\right) = O(\ell\sqrt{\ell}).$$