Самый короткий палиндром

Источник: https://leetcode.com/problems/shortest-palindrome/ 

в гугл таблицах от 23.01.2020

Дана строка s. Вы можете конвертировать s в палиндром, если добавите необходимые символы в начало строки.

Вернуть самый короткий палиндром, который можно построить при помощи описанной трансформации.

Пример 1:

Дано: s = "aacecaaa"
Результат: "aaacecaaa"
Пояснение: добавили символ а в начале строки.

Пример 2:

Input: s = "abcd"
Output: "dcbabcd"
Пояснение: добавили символы dcb в начале строки.

Ограничения:

• 0 <= s.length <= 5 * 104
• s состоит из маленьких латинских букв английского алфавита.

Идея решения

Если представить, что строка s=AB, где А - это палиндром, то тогда нам нужно добавить развернуют строку B в начало s, чтобы получить результат. То есть результат = B'AB, где B' - это развернутая строка.

Как найти А? Надо склеить строку с её частями по-другому: построим q=A'B'BA. Но поскольку А - палиндром, то есть А=А', то алгорим вырисовывается таким:

1. берем два указателя. Один ставим на нулевой  элемент строки q. Второй указатель первоначально ставится на нулевой элемент строки.
2. Параллельно сдвигаем оба указателя и смотрим, совпадают ли значения элементов строки, на который они указывают. 
1. Если совпадают, то увеличиваем счётчик.
2. Если не сопадают, то сдвигаем левый указатель опять на начало строки q.
3. В конце концов мы "поймаем" комбинацию указателей,  когда второй указатель встанет на начало строки A и оба указателя дружно просканируют A' и A, пока второй указатель не достигнет строки q. При этом значение счетчика будет показывать длину подстроки A в исходной строке s.
   

Java-имплементация

class Solution {
    public String shortestPalindrome(String s) {
        String r = new StringBuilder(s).reverse().toString();
        int[] lps = getLPS(s + '|' + r);
        return r.substring(0, r.length() - lps[lps.length - 1])  /*s'-A=B'*/+ s /*AB*/; // -> B'AB
    }
    
  
    private int[] getLPS(String s) {
      int[] lps = new int[s.length()];
      int i = 1, len = 0;
      
      while (i < s.length()) {
// значения двух указателей совпадают, сдвигаем их параллельно и увеличиваем счетчи
        if (s.charAt(i) == s.charAt(len)) // 1
          lps[i++] = ++len;
        else if (len == 0)   //  2 - первый указатель в нулевом элементе,
// значит длина префикса-палиндрома нулевая             
          lps[i++] = 0;
        else // 3 - есть некий префикс-палиндром, но значения в указателях не совпадают
//  укорачиваем палиндром, если существует более короткая версия
// (иначе первый указатель всё равно обнулится)                         
          len = lps[len - 1];
      }
      
      return lps;
    }
}

Например, в строке return lps у нас вот такое состояние:

s:  "a a c e c a a a | a a  a  c  e  c  a  a"

     0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

lps:[0,1,0,0,0,1,2,2,0,1, 2, 2, 3, 4, 5, 6, 7]

То есть каждое значение lps[i] показвает, некую длину len такую, что s(i-len, i)=s(0, len).

Когда i=11, len=2, s[i]=a, s[len]=c.
lps[len-1]=lps[1]=1
то есть мы сдвигаем первый указатель до индекса 1, поскольку предполагаем,
что s[11] мог бы быть концов префикса aa.

 

Апдейт.

Сканируем BrArAB, Ar - палиндром

Надо найти максимальный индекс x, начало строки Ar. Ar=A, len(Ar)=len(A)

Вернуть BrAB