И снова всем привет! Недавно, решая задачу 1937 с Timus'a (кстати, и вам советую! Отличная возможность отточить умения в строковых алгоритмах сразу в нескольких направлениях), я столкнулся с необходимостью нахождения всех подпалиндромов в строке. Опытные программисты уже знают, что одним из лучших алгоритмов для этого является алгоритм Манакера, позволяющий получить все подпалиндромы в сжатом виде без каких-либо дополнительных структур. Единственная проблема — алгоритм сравнительно сложен в реализации. То есть, его идея проста и понятна, а вот реализации обычно оказываются нагромождениями кода с повсеместным рассмотрением того, где написать +1, а где -1.

Для тех, кто не знает, или не помнит, опишу вкратце алгоритм Манакера. Сжатость по памяти в нём достигается за счёт того, что мы не храним индексы палиндромов, а для каждого элемента в строке храним половину длины наибольшего палиндрома, для которого он является центральным. Если речь идёт о палиндромах чётной длины, то центральным мы для удобства считаем элемент, который находится справа от центра. Скорее всего, с некоторыми изменениями таковым можно считать и тот, который находится слева.

Далее мы поддерживаем левый и правый окончания самого правого из известных палиндромов и, подобно тому, как это делается в Z-функции, мы сначала пытаемся инициализировать значение массива в этой точке, используя уже посчитанную информацию, а потом продолжаем действовать наивным алгоритмом. Если быть точным, мы можем проинициализировать значение p[i] значением в точке, симметричной относительно неё в имеющемся палиндроме, то есть, значением p[l + (r - i)]. Если речь о палиндромах чётной длины (вы уже тоже их ненавидите, да?), то нас будет интересовать значение в точке p[l + (r - i) + 1]. И да, стоит не забывать, что мы при инициализации не должны будем выйти за пределы известной нам части, то есть, инициализировать надо чем-то, что не больше, чем r - i (или r - i + 1 для палиндромов чётной длины).

Вот так нам предлагает строить алгоритм Манакера на e-maxx:

vector<int> d1 (n);
int l=0, r=-1;
for (int i=0; i<n; ++i) {
	int k = (i>r ? 0 : min (d1[l+r-i], r-i)) + 1;
	while (i+k < n && i-k >= 0 && s[i+k] == s[i-k])  ++k;
	d1[i] = k--;
	if (i+k > r)
		l = i-k,  r = i+k;
}
vector<int> d2 (n);
l=0, r=-1;
for (int i=0; i<n; ++i) {
	int k = (i>r ? 0 : min (d2[l+r-i+1], r-i+1)) + 1;
	while (i+k-1 < n && i-k >= 0 && s[i+k-1] == s[i-k])  ++k;
	d2[i] = --k;
	if (i+k-1 > r)
		l = i-k,  r = i+k-1;
}

Два отдельных похожих куска кода для палиндромов чётной и нечётной длины. И, если мне не изменяет память и это до сих пор не исправили, в них ещё и содержится ошибка (сможете её найти?)

Немного подумав и расписав некоторые случаи на листке бумаги, я смог сжать два отдельных куска в один, объединённый циклами. При этом, я постарался сохранить максимальную схожесть с алгоритмом построения Z-функции для мнемоничности.

    vector<vector<int>> p(2,vector<int>(n,0));
    for(int z=0,l=0,r=0;z<2;z++,l=0,r=0)
        for(int i=0;i<n;i++)
        {
            if(i<r) p[z][i]=min(r-i+!z,p[z][l+r-i+!z]);
            while(i-p[z][i]-1>=0 && i+p[z][i]+1-!z<n && s[i-p[z][i]-1]==s[i+p[z][i]+1-!z]) p[z][i]++;
            if(i+p[z][i]-!z>r) l=i-p[z][i],r=i+p[z][i]-!z;
        }
    }

Однако, всю картину портит достаточно длинная строка с while. С этим я предлагаю бороться примерно таким образом:

    vector<vector<int>> p(2,vector<int>(n,0));
    for(int z=0,l=0,r=0;z<2;z++,l=0,r=0)
        for(int i=0;i<n;i++)
        {
            if(i<r) p[z][i]=min(r-i+!z,p[z][l+r-i+!z]);
            int L=i-p[z][i], R=i+p[z][i]-!z;
            while(L-1>=0 && R+1<n && s[L-1]==s[R+1]) p[z][i]++,L--,R++;
            if(R>r) l=L,r=R;
        }

Как кажется лично мне, в таком виде код является наиболее читаемым и так в нём труднее всего допустить какую-то ошибку. А что думаете по этому поводу вы? Как реализовывать Манакера наименее мучительно? И вообще, как вы решаете задачу поиска всех подпалиндромов в строке? Поделитесь своими идеями в комментариях :)

UPD: droptable в комментариях рассказал о способе поддерживать массивы из алгоритма Манакера в онлайне. Здесь я выложил пример использования самого алгоритма с некоторыми изменениями, о которых будет сказано ниже.

Основная идея алгоритма: в любой момент мы поддерживаем центр максимального суффикс-палиндрома. Когда мы добавляем символ в конец, у нас есть два варианта того, что произойдёт дальше:

1. Основной палиндром расширится. Тогда просто увеличиваем для него значение радиуса на единицу и на этом завершаем.
2. Основной палиндром не расширится. Это значит, что нам нужно будет пройтись по массиву вперёд, чтобы найти новый основной палиндром. При этом каждый раз инициализируем новую ячейку в массиве числом в ячейке, симметричной относительно центра палиндрома, который был основным ранее. Как только оказалось, что мы можем расширить текущий палиндром, это означает, что он самый левый из касающихся конца строки, а значит, он станет новым основным. Завершаем на этом обновление.

Теперь об изменениях в коде. Во-первых, были убраны два символа-заглушки, которые вставлялись в строку вначале. Как оказалось, они не являются необходимыми, однако, их добавление усложняет алгоритм.

Во-вторых была добавлена функция get(). Михаил упоминал в своём комментарии некоторые проблемы с онлайном. Проблема была в том, что в любой момент мы знаем окончательные значения только в элементах, которые находятся ранее, чем центр основного палиндрома. Однако, можно заметить, что значения за ним мы можем получать за О(1), обратившись к симметричному относительно центра палиндрома элементу.