Алгоритмы для поиска палиндромов

image

Сегодня я хочу вам рассказать об алгоритмах подсчёта количества палиндромов в строке: для чего это нужно, где применяется, как это быстро сделать, какие подводные камни нас ожидают и многое другое. Рассмотрим различные способы для решения данной задачи, выясним плюсы и минусы каждого способа. Эта статья будет обзорной: если я что-то не описываю здесь, то постараюсь всегда дать вам набор ссылок, где всё подробно описано и расписано. Надеюсь, что материал будет интересен как новичкам в сфере алгоритмов, так и матёрым программистам. Что же, если я смог заинтересовать вас, то прошу под кат!

Для начала стоит вспомнить, что же такое палиндром.

Палиндро́м — число (например, 404), буквосочетание, слово или текст, одинаково читающееся в обоих направлениях. Иногда палиндромом называют любой симметричный относительно своей середины набор символов.(выдержка из Википедии)

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

Для чего может потребоваться искать палиндромы?

На самом деле, не очень то и часто приходится искать палиндромы в повседневной жизни. Уж больно специфичная это задача. Если говорить о строковых алгоритмах, то мы намного чаще встречаем тот же поиск подстроки в строке, чем нахождение количества палиндромов. Поэтому и освещение в литературе намного слабее.

Одно из основных применений — спортивное/олимпиадное программирование. Там задач на такое хватает. Задач понаписывают, а участникам уже думай, каким способом это решить. Из личного опыта скажу, что мне такие задачи встречались всего пару раз, но все они были из разряда «вот тебе задача, ты не думай, а просто напиши алгоритм». То есть не интересные задачи, которые развивают просто механическую память по набиванию алгоритмов.

А более практическое применение нахождения палиндромов — это биологические алгоритмы. Согласно всё той же Википедии и ссылкам снизу Вики, палиндромность биологических соединений играет важную роль на свойствах различных биологических соединений. Я в биологии слаб, поэтому если вам интересно, то вы можете найти более подробную информацию сами.

Отлично, мы выяснили, что мы будем заниматься не совсем бесполезными делами. Давайте же уже перейдем к рассмотрению алгоритмов!

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

0) Самый банальный алгоритм с асимптотикой O(N^3)


bool SlowN3::isPalindrom(int leftBorder, int rightBorder)
{
    while(leftBorder <= rightBorder)
    {
        if(str[leftBorder] != str[rightBorder])
        {
            return false;
        }
        ++leftBorder;
        --rightBorder;
    }
    return true;
}

long long SlowN3::operator ()()
{
    for(int leftBorder = 0;leftBorder < str.length(); ++leftBorder)
    {
        for(int rightBorder = leftBorder + 1; rightBorder < str.length(); ++rightBorder)
        {
            if( isPalindrom(leftBorder, rightBorder) )
            {
                ++cntPalindromes;
            }
        }
    }
    return cntPalindromes;
}

Хочу предупредить сразу, что все исходники будут на C++, и это будут значимые части классов, которые нам могут быть интересны.

Алгоритм самый что ни на есть «лоб»: имеется строка, есть указатель на начало подстроки данной строки, есть указатель на конец данной подстроки. В двух вложенных циклах перебираем границы подстрок и банально проверяем, является ли наша подстрока палиндромом. Ничего сложного.

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

Плюсов у данного способа немного:

+ Легко реализуется. Действительно, оставить багу здесь ну очень сложно.
+ Легко читается. Вы только взглянули, и уже поняли, что да как здесь работает.
+ Малая скрытая константа. Как известно, на время работы алгоритма влияет не только асимптотическая оценка (здесь мы работаем только с худшими случаями), но и скрытая константа. У этого алгоритма скрытая константа крайне мала.

Минусы:

— Крайне малая скорость работы. Как вы можете видеть, что при строке из тысячи букв 'a' данный алгоритм сделает порядка 10^9 итераций, что есть очень плохо. А что если строка длиной 100000?

1) Самый банальный алгоритм с асимптотикой O(N^2)


Код:

void SlowN2::oddCount()
{
    for(int indMiddle = 0; indMiddle < str.length(); ++indMiddle)
    {
        int leftBorder = indMiddle - 1, rightBorder = indMiddle + 1;
        while(leftBorder >= 0 && rightBorder < str.length() && str[leftBorder] == str[rightBorder])
        {
            ++cntPalindromes;
            --leftBorder;
            ++rightBorder;
        }
    }
}

void SlowN2::evenCount()
{
    for(int indMiddle = 0; indMiddle < str.length(); ++indMiddle)
    {
        int leftBorder = indMiddle, rightBorder = indMiddle + 1;
        while(leftBorder >= 0 && rightBorder < str.length() && str[leftBorder] == str[rightBorder])
        {
            ++cntPalindromes;
            --leftBorder;
            ++rightBorder;
        }
    }
}

Здесь уже чуточку интереснее. У нас имеется строка, и два временных массива для палиндромов чётной и нечётной длины. А число в ячейке i массива будет хранить количество палиндромов в строке s(исходная строка) с центром в точке i. Для нечётной длины палиндрома центр находится легко, ну а для чётной мы просто чуть поиграемся с индексами и сместим чуточку центр(что видно в коде). Наш результат это есть сумма чисел из двух массивов.

Как видите, снова ничего сложного. Но работает это заметно быстрее предыдущего алгоритма. Почему? Давайте рассмотрим, как же оно всё работает.

Мы бежим по строке, перебирая центральный символ нашего потенциального палиндрома. А потом просто бежим влево и вправо от центрального элемента до тех пор, пока символы одинаковы. Как только они стали разными, это значит, что дальше не будет палиндромов с центром в нашем выбранном элементе, и переходим к следующему.

А работает это быстро на обычных строках очень быстро потому, что наш второй, вложенный цикл, который бежит до тех пор, пока крайние символы равны, обрывается крайне быстро(если предположить, что палиндромов в строке много меньше общего числа подстрок).

Рассмотрим плюсы и минусы способа.

Плюсы:

+ Всё также легко кодится. Ошибиться очень сложно.
+ Малая скрытая константа
+ Хорошо ведёт себя на случайных строках

Минусы:

— Всё ещё долгое время работы

После этого способа уже голова начинает думать-думать-думать. И тут идея! А что если мы модифицируем этот способ, только будем от центрального элемента прыгать не на 1 символ с каждой итерацией, а на чуточку больше? И тут нам на помощь приходят…

2) Используем хеши!


Этот способ чуточку сложнее, поэтому сразу приведу код, а потом постараюсь обьяснить, что за магия там творится(хотя магии нет, как вы сами прекрасно знаете):

inline long long Hash::getHash(int indLeft, int indRight) const
{
    return prefixHash[indRight] - (indLeft > 0 ? prefixHash[indLeft - 1] : 0);
}

inline long long Hash::getRevHash(int indLeft, int indRight) const
{
    return suffixHash[indLeft] - (indRight < suffixHash.size() - 1 ? suffixHash[indRight + 1] : 0);
}

void Hash::PrepareSimpleNumbers()
{
    if(str.length() > simpleNumbers.size())
    {
        size_t oldSize = simpleNumbers.size();
        simpleNumbers.resize(str.length());
        simpleNumbers[0] = 1LL;
        for(int i = oldSize; i < simpleNumbers.size(); ++i)
            simpleNumbers[i] = simpleNumbers[i - 1] * SimpleBase;
    }
}

void Hash::CountingPrefixHash()
{
    prefixHash[0] = str[0];
    for(int i = 1; i < prefixHash.size(); ++i)
    {
        prefixHash[i] = prefixHash[i - 1] + str[i] * simpleNumbers[i];
    }
}

void Hash::CountingSuffixHash()
{
    suffixHash[suffixHash.size() - 1] = str[str.length() - 1];
    for(int i = (int) str.length() - 2, j = 1; i >= 0; --i, ++j)
    {
        suffixHash[i] = suffixHash[i + 1] + str[i] * simpleNumbers[j];
    }
}

bool Hash::isPalindrome(int indLeft, int indRight) const
{
    return getHash(indLeft, indRight) * simpleNumbers[prefixHash.size() - indRight - 1] ==
           getRevHash(indLeft, indRight) * simpleNumbers[indLeft];
}

void Hash::CountingOdd()
{
    for (int i = 0; i < oddCount.size(); i++)
    {
        int indLeft = 1, indRight = min(i + 1, static_cast<int> (oddCount.size() - i));
        while (indLeft <= indRight)
        {
            int middle = (indLeft + indRight) / 2;
            if (isPalindrome(i - middle + 1, i + middle - 1))
            {
                oddCount[i] = middle - 1;
                indLeft = middle + 1;
            }
            else
            {
                indRight = middle - 1;
            }
        }
    }
}

void Hash::CountingEven()
{
    for (int i = 0; i < evenCount.size(); i++)
    {
        int indLeft = 1, indRight = min(i, static_cast<int> (evenCount.size() - i));
        while (indLeft <= indRight)
        {
            int middle = (indLeft + indRight) / 2;
            if (isPalindrome(i - middle, i + middle - 1))
            {
                evenCount[i] = middle;
                indLeft = middle + 1;
            }
            else
            {
                indRight = middle - 1;
            }
        }
    }
}

long long Hash::operator()()
{
    PrepareSimpleNumbers();
    CountingPrefixHash();
    CountingSuffixHash();
    CountingOdd();
    CountingEven();
    for(int i = 0; i < str.length(); ++i)
    {
        cntPalindromes += oddCount[i] + evenCount[i];
    }
    return cntPalindromes;
}

Краткая суть данного способа: мы перебираем центральный элемент нашего палиндрома, и потом дихотомией стараемся найти наибольший радиус нашего палиндрома (под радиусом здесь понимается расстояние от центрального элемента до крайнего, если у нас палиндром чётной длины, то просто добавим чуточку игры с индексами, чтобы всё работало). Во время подбора мы должны как-то быстро сравнивать подстроки на идентичность. делаем это с помощью хешей. Асимптотика, как легко догадаться: N тратим на перебор центрального элемента, logN в худшем случае тратим на подбор радиуса палиндрома, за единицу сравниваем подстроки с помощью хешей. Итого имеем O(NlogN), что очень даже неплохо на самом деле.

Теперь чуть подробнее остановимся на данном методе.

На чём основывается наш метод? Так как мы перебираем центральный элемент, а потом дихотомией подбираем радиус наибольшего палиндрома с центром в данном элементе, то мы должны быстро брать хеш левой части нашего потенциального палиндрома и сравнивать его с хешем правой части нашего потенциального палиндрома.

Как это сделать? Давайте предварительно рассчитаем хеш для каждого префикса и суффикса исходной строки. В коде это у нас делают методы CountingPrefixHash() и CountingSuffixHash() соответственно.

С помощью методов getHash() и getRevHash() мы можем быстро получить хеши левой и правой частей рассматриваемого на данном этапе потенциального палиндрома. Тут может возникнуть вопрос, почему нельзя воспользоваться одной и той же функцией подсчёта хеша для левой и правой частей. А всё потому, что мы при проверке на палиндромность левую часть мы читаем слева направо, а вторую справа налево. И нам необходимо поддерживать хеш слева направо и справа налево.

Осталась единственная сложность: как сравнить этих 2 хеша? И эту проблему мы решаем с помощью метода isPalindrome(), который приводит хеши к одному основанию и сравнивает их.

Результатом каждой итерации у нас будет количество палиндромов с центром i. Пробегаемся 2 раза для палиндромов чётной и нечётной длины, ответ на нашу задачу есть сумма всех значений массивов oddCount и evenCount

Более подробно про данный метод вы можете почитать в этой статье.

Плюсы:

+ Асимптотически мы снизили до NlogN, что не может не радовать. Если брать только худшие случаи, то в теории когда-нибудь мы выиграем

Минусы:

— Довольно тяжело пишется. Легко посеять багу. Нужна немного теоретическая подготовка в области хешей.
— Медленно работает на случайных тестах. Вы можете сами в этом убедиться. А всё из-за большой скрытой константы и из-за того, что даже если у нас нет ни одного палиндрома с центром в данном элементе, то алгоритм сделает logN прыжков, а это всё занимает время.
— Коллизии. Как вы видите, в моём исходнике используется хеш, который обычно пишут на олимпиадах по программированию(да-да, я немного этим когда-то занимался). Так вот, на соревнованиях данный способ показывает себя хорошо. Лично у меня коллизии не случались. Но я знаю про способы спокойно данный хеш завалить(в частности способ с использованием строк Туэ-Морса). Я когда-то слышал, что есть какой-то фиббоначиевый хеш, который вроде бы не ломается на данном тесте, но информация недостоверная. Так что будьте осторожны с коллизиями.

А если мы хотим 100% решение без всякой там коллизийной поправки и ввода хеша по другому основанию и так далее?

3) Алгоритм Манакера


Код:

//Find palindroms like 2*N+1
void Manacker::PalN2()
{
    int leftBorder = 0, rightBorder = -1, tempMirror;//start digits for algortihm
    for(int i = 0; i < str.length(); ++i)
    {
        tempMirror = (i > rightBorder ? 0 : std::min(ansPalN2[leftBorder + rightBorder - i], 
                                                                            rightBorder - i)) + 1;//find mirror of current index
        while(i + tempMirror < str.length() && i - tempMirror >= 0 && 
                 str[i - tempMirror] == str[i + tempMirror])//increase our index
        {
            ++tempMirror;
        }
        ansPalN2[i] = --tempMirror;
        if(i + tempMirror > rightBorder)//try to increase our right border of palindrom
        {
            leftBorder = i - tempMirror;
            rightBorder = i + tempMirror;
        }
    }
}

void Manacker::Pal2()
{
    int leftBorder = 0, rightBorder = -1, tempMirror;
    for(int i = 0; i < str.length(); ++i)
    {
        tempMirror = (i > rightBorder ? 0 : std::min(ansPal2[leftBorder + rightBorder - i + 1],
                                                                            rightBorder - i + 1)) + 1;
        while(i + tempMirror - 1 < str.length() && 
                  i - tempMirror >= 0 && str[i - tempMirror] == str[i + tempMirror - 1])
        {
            ++tempMirror;
        }
        ansPal2[i] = --tempMirror;
        if(i + tempMirror - 1 > rightBorder)
        {
            leftBorder = i - tempMirror;
            rightBorder = i + tempMirror - 1;
        }
    }
}

Итак, мы получили с помощью хешей алгоритм за NlogN. Но хочется быстрее. Хочется чего-то линейного. И тут нам на помощь спешит Алгоритм Манакера (по ссылке вы также можете видеть реализацию алгоритма на Java), который мало того, что линеен, так ещё и обладает крайне малой скрытой константой, что положительно сказывается на его скорости работы. Подробно описывать способ я не буду, так как это получится пересказ этой замечательной ссылки (я сам учил алгоритм именно по этой ссылке). Здесь я приведу слегка пересказанное объяснение.

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

Что ещё интересного: во всех задачах, которые я решал на контестах (по олимпиадному программированию), хватало именно этого алгоритма. Очень просто пишется, если ты его писал N раз дома и уже знаешь наизусть.

Плюсы:

+ Довольно короткий код.
+ Очень быстро работает. Мало того, что асимптотика O(N), так ещё и малая скрытая константа.

Минусы:

— Идея не такая простая, чтобы самому сходу придумать данный алгоритм
— Можно запутаться во всяких индексах, если проявить невнимательность при написании кода

А есть ли другие способы решить данную задачу за линейное время?

4) Дерево палиндромов


Немного предыстории. Эту относительно новую структуру данных открыл Михаил Рубинчик rumi13 и представил её на Петрозаводских сборах. Структура крайне интересная своей с одной стороны простотой, а с другой тем, что позволяет быстро решать довольно широкий спектр задачи про палиндромы. И самое главное — позволяет довольно просто считать количество палиндромов в строке за O(N) (но само дерево палиндромов думаю придумывалось далеко не для этого, а для более серьёзных задач с палиндромами).

Код:

PalindromicTree::PalindromicTree(const std::string& s) : FindPalindrome(s)
{
    initTree();
}

PalindromicTree::~PalindromicTree()
{
    for(int i = 0;i < pullWorkNodes.size(); ++i)
    {
        delete pullWorkNodes[i];
    }
}

void PalindromicTree::initTree()
{
    root1 = new Node;
    root1->len = -1;
    root1->sufflink = root1;
    root2 = new Node;
    root2->len = 0;
    root2->sufflink = root1;
    suff = root2;
    pullWorkNodes.push_back(root1);
    pullWorkNodes.push_back(root2);
}

void PalindromicTree::findAddSuffix(Node* &cur, int pos, int& curlen)
{
    while (true)
    {
        curlen = cur->len;
        if (pos - 1 - curlen >= 0 && str[pos - 1 - curlen] == str[pos])
        {
            break;
        }
        cur = cur->sufflink;
    }
}

void PalindromicTree::makeSuffixLink(Node* &cur, int pos, int& curlen,int let)
{
    while (true)
    {
        cur = cur->sufflink;
        curlen = cur->len;
        if (pos - 1 - curlen >= 0 && str[pos - 1 - curlen] == str[pos])
        {
            suff->sufflink = cur->next[let];
            break;
        }
    }
}

void PalindromicTree::addLetter(int pos)
{
    Node* cur = suff;
    int let = str[pos] - 'a', curlen = 0;
    findAddSuffix(cur, pos, curlen);
    if (cur->next[let] != nullptr)
    {
        suff = cur->next[let];
        return;
    }
    suff = new Node;
    pullWorkNodes.push_back(suff);
    suff->len = cur->len + 2;
    cur->next[let] = suff;
    if (suff->len == 1)
    {
        suff->sufflink = root2;
        suff->num = 1;
        return;
    }
    makeSuffixLink(cur, pos, curlen, let);
    suff->num = 1 + suff->sufflink->num;
}

long long PalindromicTree::operator ()()
{
    for (int i = 0; i < str.length(); ++i)
    {
        addLetter(i);
        cntPalindromes += suff->num - 1;
    }
    return cntPalindromes;
}

Опять же, перескажу вкратце суть данного алгоритма. С более подробным разъяснением вы можете ознакомиться в этой замечательной статье.

Итак, идея дерева. В вершинах нашего дерева будут находиться только сами палиндромы: 'a', 'b', 'aba' и так далее. Понятно, что сам палиндромы мы не будем хранить, а просто будем хранить из какой вершины мы пришли сюда, и какой символ с двух сторон добавили. Также у нас существуют две фиктивные вершины для удобной реализации алгоритма.

Но как и в любом интересном дереве, у нас также существуют суффиксные ссылки. Суффиксная ссылка будет вести в вершину, которая также является палиндромом (ну потому что у нас в вершинах хранятся только палиндромы) и которая является наибольшим собственным суффиксом данной вершины. То есть из вершины 'aba' ссылка будет вести в вершину 'a'.

Далее, мы по очереди добавляем символы в дерево по одному. И благодаря хитрому устройству дерева и рекурсивной операции добавления (а также суффиксным ссылкам, по которым осуществляется переход), мы обновляем всё дерево.

Это вкратце, подробнее почитайте информацию по ссылке выше (если не боитесь английского)

Плюсы:

+ Если Вы ранее работали с деревьями, то вам будет очень просто понять данную идею.
+ Позволяет решать большой спектр задач на палиндромы

Минусы:

— Работает медленнее, чем алгоритм Манакера.
— Можно поставить багу. Но, чисто субъективно, тут это сделать сложнее, чем в том же алгоритме Манакера.

Также стоит упомянуть, что с помощью деревьев существует ещё одно решение данной задачи. Оно заключается в использовании суффиксного дерева и быстрого алгоритма LCA(который работает за препроцессинг O(N) и ответ на запрос O(1). Алгоритм Фарах-Колтон-Бендера). Но он на практике не применяется, так как довольно сложен и у него крайне большая скрытая константа. Представляет скорее академический интерес.

Что может быть ещё интересно про алгоритмы? Правильно, потребление памяти и время работы.
На гитхабе Вы можете скачать также код для тестирования, который генерирует случайные строки и ищет в них палиндромы.

Моё тестирование показало, что ожидаемо алгоритм номер 0 работает крайне медленно. Лидером, как Вы можете догадаться, является алгоритм Манакера. Но что самое интересное: алгоритм с O(N^2) выигрывает с примерно двукратным отрывом у алгоритма с использованием хешей с O(NlogN), что ещё раз доказывает, что не асимптотикой единой меряются алгоритмы. Так происходит из-за особенностей отсечения алгоритма номер 1, и отсутствия оной в способе с хешами. Что касается дерева палиндромов, то оно проигрывает Манакеру в основном из-за операций с памятью, так как приходится выделять память под каждую новую вершину. Но если использовать, например, new с размещением, то разрыв сократится.

Память все алгоритмы потребляют линейно от размера входных данных.

На этом мы завершим наш обзор. Надеюсь, что вы почерпнули для себя хоть что-то новое и вам было хоть чуточку интересно! Все исходники вы можете найти в моём публичном репозитории на Github.

P.S.: Если вы заметили какие-то опечатки, неточности или у вас есть дополнения — прошу отписываться в комментариях и писать в ЛС.
P.P.S.: Смело задавайте вопросы в комментариях — постараюсь ответить, если хватит моей компетенции.

Полезные ссылки, которые могут быть вам интересны после прочтения данной статьи (некоторые ссылки могут повторяться, так как могли проскакивать в самой статье):

0) Что такое палиндром
1) Алгоритм Манакера: Вики, Codeforces, e-maxx
2) Немного про хеши и их применение: e-maxx, Habrahabr
3) Обсуждение про завал хешей на Codeforces: тыц
4) Строки (слова) Туэ-Морса: раз, два
5) Статьи про дерево палиндромов: хорошее описание, codeforces
6) Вот ещё цикл статей про поиск чисел-палиндромов: Хабр
Share post
AdBlock has stolen the banner, but banners are not teeth — they will be back

More
Ads

Comments 26

    0
    Еще бы алгоритм составления осмысленных палиндромов ;)
      +3
      эххх, хотя бы для начала просто осмысленность научиться программировать :)
        0
        Ну, не скажите. Со словарем, имхо, не такая уж сложная задача…
          0
          может я не совсем понял, что Вы понимаете под «составлением осмысленного палиндрома»? я задачу понял, как генерацию палиндрома-предложения аля «А роза упала на лапу Азора». То есть у нас есть словарь, и мы должны из слов составить предложение, которое является палиндромом. Какие тут трудности могут возникнуть (первое, что приходит в голову):
          0) Осмысленность. Просто рандомные слова мы подставлять не можем. Смысла скорее всего не будет, а чекера на «осмысленность» я придумать что-то не могу. В языке есть порядок слов. Но даже если соблюдать порядок, то не все слова сочетаются друг с другом.

          Попробуем решить данную проблему. У нас есть пулл слов. Соединим их связями, какие слова с какими могут быть связаны. (пример слова «бить» и «воздух» связаны не будут(что-то не могу я их связать в голове), а вот «бить» и «баклуши» связаны) Можно также ввести вес связи — чем тяжелее, тем лучше подходит слово одно к другому. Можно попробовать ввести показатель, где лучше слову стоять от связанного с ним: слева или справа. Можно много чего ещё…

          Но это сложно всё. Да и как соптимизировать это по скорости, я не представляю пока. Может из слов какой граф построить… Не знаю, не знаю.
            +1
            Насчёт весов — обработать какой-нибудь крупный корпус и дать веса парам/тройкам/«n-грамма»-like наборам слов, в духе «что за чем часто идёт». Это, конечно, не покроет все варианты порядка слов в языке, и при генерации палиндромов будут простые самые популярные варианты. Примерно так, судя по всему, работает например Свифткей и другие дополняющие клавиатуры.
              0
              да, с таким способом я знаком. Может у Вас есть какие идеи по поводу генерации палиндромных строк? Потому что в моём представлении всё это будет работать ужасно медленно.
                0
                Пока что всё, что приходит в голову с ходу — ужасно медленное :) Для начала — каждое слово развернуть и посмотреть, есть ли в словаре оно развернутое или любая его подстрока (не одна буква конечно, и видимо даже не две, а например с трёх), и — что более проблематично по времени — пересечь все подстроки со всеми словами в словаре и запомнить, с какими словами его можно совмещать в смысле симметрии вокруг центра палиндрома, и что еще более проблематично — с каким набором слов (например, "<что-то, заканчивающееся на -н> упала" — «на лапу»). Радует только, что это всё одноразовый препроцессинг, и вот потом уже из получившейся базы искать популярные словосочетания, начиная с рандомного слова.
                  0
                  Это всё ужасно затратно по препроцессингу. и памяти нужно много. и мои подсчёты мне подсказывают, что время на препроцессинг и ресурсов уйдёт уйма :)
      –7
      Сам недавно реализовывал подобное. Ожидал увидеть тут решение с инвертированием строки и сравнением ее с исходной. Кажется, что это самый простой и очевидный способ.
        +1
        Здесь решается другая задача — поиск подстрок, которые являются палиндромами. Вы скорее всего просто проверяли, является ли входная строка палиндромом. Очевидное решение вашей задачи — это пробежаться циклом до середины строки, сравнивая первый символ с последним, второй символ с предпоследним и т.д. То решение, что предложили вы, потребует выделения лишней памяти на перевёрнутую версию строки, время на «переворачивание» строки при копировании одной строки в другую, время на последующее сравнение двух строк и освобождение памяти, занимаемой временной строкой. Уж не знаю, как вы решили, что это всё проще одного коротенького цикла.
          0
          https://github.com/Areso/Palindrome-searcher/blob/master/unit1.pas вот такая была у меня реализация вашей идеи. Хотя соглашусь с VEG, его вариант выглядит изящнее в плане расхода ресурсов.
          –1
          Мне кажется что задекларированная в статье цель:
          Сегодня я хочу вам рассказать об алгоритмах подсчёта количества палиндромов в строке

          немного не соответствует тексту и обсуждению, т.к. мы получаем множество палиндромов и выводим их количество. В текстах на Си ( я язык Си не знаю ) результатом является cntPalindromes — количество палиндромов в строке. Для расчета количества палиндромов это избыточно.
          Если нужно просто подсчитать количество палиндромов в строке, достаточно простейшего цикла по строке, с раздельным подсчетом количества четных и нечетных.
          четные добавляются, когда следующий символ = текущему символу
          нечетные добавляются, когда следующий символ = предыдущему символу
          +
          Если анализируется естественный текст, например >А роза упала на лапу Азора<
          надо игнорировать пробелы и знаки препинания
            0
            Эмм, что-то я не совсем понял, как работает Ваш алгоритм. Можете подробнее? :) просто если я правильно понял, то Вы имеете в виду алгоритм под номером 1). Он работает за N^2. Есть алгоритмы быстрее(тот же Манакер, что есть в статье). Или мы говорим о разных вещах?
              –1
              Вы меня неправильно поняли, еще раз повторяю:
              для получения количества палиндромов совсем не обязательно формировать их множество, достаточно просто посчитать сколько в строке середин, четные и нечетные можно считать отдельно.
              // paliandr project main.go
              package main
              import (
              	"fmt"
              )
              func main() {
              	//	slowo := "banan"
              	slowo := "arozaupalanalapyazora"
              	slowo = "banan"
              	var count_chet, count_nechet int
              	for ii := 0; ii < len(slowo); ii++ {
              		if ii+1 < len(slowo) {
              			if slowo[ii] == slowo[ii+1] {
              				count_chet++
              			}
              			if ii > 0 {
              				if slowo[ii-1] == slowo[ii+1] {
              					count_nechet++
              				}
              			}
              		}
              	}
              	fmt.Println(count_chet, count_nechet)
              }
              
                0
                Вы конечно извините, но Ваш алгоритм неверен, и я Вам это сейчас продемонстрирую. Ваш алгоритм на строке «abacabakar» выводит, что в строке всегго 4 палиндрома, но на самом деле их там 6 (шесть). По крайней мере как минимум столько я их там сходу насчитал. Ваш код на Go я не запускал, запускал вот это (абсолютно идентичный код на C\C++, приведён ниже):
                #include <bits/stdc++.h>
                
                using namespace std;
                
                int main()
                {
                    string s = "abacabakar";
                    int chet_count = 0, nechet_count = 0;
                    for(int i = 0;i < s.length(); ++i)
                    {
                        if(i + 1 < s.length())
                        {
                            if(s[i] == s[i+1])
                            {
                                chet_count++;
                            }
                            if(i > 0)
                            {
                                if(s[i-1] == s[i+1])
                                {
                                    nechet_count++;
                                }
                            }
                        }
                    }
                    cout << chet_count + nechet_count;
                    return 0;
                }
                


                Или я что-то протестировал не так? Естессно, палиндромы длины 1 мы не учитываем.
                  –1
                  просто вы в строке «abacaba» находите 3 палиндрома aca bacab abacaba
                  а я один, маленькие порождение, часть большого. Для анализа данных, с моей точки зрения, наибольший интерес представляют наиболее длинные цепочки
                    0
                    Э, не, не лукавьте :) Это с Вашей точки зрения. Есть чёткая задача — найти количество палиндромов в строке. (Да, я внёс некоторые слабинки в коде: работаю не с Юникодом, не удаляю пробелы и иные знаки препинания. Но это всё не сказывается на асимптотической сложности алгоритмов. А просто добавляет чуточку времени на препроцессинг строки.)

                    Вернемся к нашему заданию. Даже не количество различных палиндромов, а просто их общее количество. Чёткое задание, которое решается алгоритмами, приведёнными в статье. Если Вы знаете другие алгоритмы — я с превеликой радостью выслушаю, постараюсь их понять, напишу код на C\C++, выложу на Github и обновлю статью, также оставлю ссылку на Ваше решение.

                    Вы же решаете какой-то частный случай. Если Ваш алгоритм чуточку модифицировать, чтобы он находил все палиндромы, а не только «наиболее длинные цепочки», то он как раз и выродится в алгоритм за O(N^2). С чем Вы, надесю, согласны :)
                      –1
                      Я не лукавлю, но я, например, считаю что текст «А роза упала на лапу Азора» это один палиндром, а не несколько.
                        0
                        Так, ещё раз о постановке задачи в данной статье. Я процитирую себя: "… об алгоритмах подсчёта количества палиндромов в строке". Тут нет слов «всех», «общего количества» или каких-то синонимов к ним. Возможно, это моё упущение, что я явно не указал это. Но лично для меня является вполне логичным предполагать, что если я сказал «подсчёта количества палиндромов», то имеется в виду именно всех палиндромов, а не каких-то там сферических в вакууме «наиболее длинных цепочек». Хочу заметить, что далее, в начале статьи, я указал, что не рассматриваю буквы-палиндромы (просто добавлять длину строки к ответу), и, как я уже писал выше, не убираю со строки всякий мусор.

                        Далее, ещё раз о "… об алгоритмах подсчёта количества палиндромов в строке". Как видите, «в строке». Это значит что, если мне на вход сразу дадут палиндром, мне в ответ единицу выводить?:) А в чём же тогда интерес данной статьи? :)

                        Ещё раз повторяю: Ваш алгоритм решает частную задачу, которая не рассматривается в данной статье. Да, алгоритм интересен, но это всё частности. Я же рассматриваю общий случай, и для этого общего случая есть алгоритм, который решает эту же задачу, что и Ваш — алгоритм Манакера. Ваш же алгоритм является некоторой его интерпретацией под частный случай. А рассмотреть все частные случаи я, к моему глубокому сожалению, не в силах, так как мало ли, у кого-то будет задача на работе «посчитать количсетво палиндромов с тремя буквами 'ё' на нечётных местах относительно центра исходной строки, смещенной на два индекса влево» :)
                          –1
                          Прошу не путать все в кучу.
                          Алгоритм Манакера позволяет за линейное время найти в строке самый длинный палиндром ...
                          .
                          (это я цитирую Вики и пр.).
                          Целью же вашей статьи является поиск количества палиндромов, а не формирование множества палиндромов.
                          Я просто пытаюсь до вас довести мысль о том что количество палиндромов можно получить не формируя их множества. Если конечно вы согласны с тем, что в словах казак, шалаш один, а не два палиндрома.
                          «А роза упала на лапу Азора» все таки один или несколько палиндромов?
                            0
                            Разберёмся по порядку. Алгоритм Манакера позволяет как найти количество палиндромов, так и самый длинный: разберитесь в алгоритме и увидите, что это решается одинаково в случае алгоритма Манакера. Так что насчёт этого алгоритма права и Вики, и я (я же учился тоже не от знаний из Вселенной:) ).

                            Насчёт формирования? Что Вы понимаете под формированием палиндрома? Если Вы имеете ввиду что-то аля «давайте запихнём все палиндромы в вектор». То есть отдельно каждый палиндром представить в виде отдельной строки, то на это уйдет O(N^2) операций. Так а как же Манакер работает? Он просто для каждого центра ищёт радиус самого большого палиндрома с центром в данном элементе (для палиндромов чётной длины происходит некоторая игра с индексами, ничего более). Это и называется поиском самого длинного палиндрома. Но через эту информацию мы также спокойно получаем общее количество палиндромов очевидным способом. Заметьте, что данный алгоритм не формирует множество, он просто считает радиус наибольшего палиндрома с центром в данном элементе, ничего более :) Формирование множества — это уже другая задача. Не храню же я в Манакере сами палиндромы или хотя бы границы КАЖДОГО найденного палиндрома в строке. Я просто храню наибольший радиус для каждого элемента. Ваш алгоритм является интерпретацией Манакера для частного случая (Вы можете заметить сходства между ним и Вашим алгоритмом. По крайней мере я их вижу отчётливо, пусть они и довольно слабы).

                            Теперь насчёт Ваших примеров. Я отвечу так: слова «казак», «шабаш» являются сами по себе палиндромами и содержат в себе палиндромы. Также как и «а роза упала на лапу азора» — это палиндром, содержащий в себе другие палиндромы. Статья моя о поиске палиндромов в строках. А значит, мне неважно, является исходная строка палиндромом или нет — я должен найти в ней ВСЕ палиндромы(включая саму строку, если она ялвяется палиндромом, естественно. Буквы я за палиндром не считал, но это несложно поправить).
                              0
                              И в рамках рассмотренных алгоритмов тот же «казак» раскладывается на 2 палиндрома. Ваша задача сферична и в вакууме, ничего более. Хоть Ваш алгоритм и показывает, как решать такую вот задачу, что похвально. Но я не могу добавить её в статью, так как это всего лишь частный случай.
              0
              SimpleBase используется в коде, но нигде не объявлено.
              0
              Не очень понял как в алгоритме с хэшами задаются размеры массивов oddCount и evenCount?

            Only users with full accounts can post comments. Log in, please.