Алгоритм Манакера: эффективный поиск палиндромов

Почему этот алгоритм важен?

Алгоритм Манакера позволяет оценить:

• ⚡ Эффективность линейных алгоритмов работы со строками
• 🧠 Технику использования ранее полученных результатов (динамическое программирование)
• 🔍 Способы оптимизации наивных решений
• 🎯 Нестандартные подходы к решению классических задач

Постановка задачи

Формулировка:

Найти все палиндромные подстроки в данной строке или найти самый длинный палиндром.

Примеры:

// Первый пример
Input: s = "babad"
Output: "bab" или "aba" // Оба являются корректными ответами

// Второй пример
Input: s = "cbbd"
Output: "bb"

// Третий пример
Input: s = "aacabdkacaa"
Output: "aca"

Проблема наивного подхода

Наивный подход к поиску самого длинного палиндрома имеет временную сложность O(n³):

function naiveLongestPalindrome(s) {
  let longest = "";
  const n = s.length;
  
  for (let i = 0; i < n; i++) {
    for (let j = i; j < n; j++) {
      const substr = s.substring(i, j + 1);
      
      // Проверяем, является ли подстрока палиндромом
      let isPalindrome = true;
      for (let k = 0; k < substr.length / 2; k++) {
        if (substr[k] !== substr[substr.length - 1 - k]) {
          isPalindrome = false;
          break;
        }
      }
      
      if (isPalindrome && substr.length > longest.length) {
        longest = substr;
      }
    }
  }
  
  return longest;
}

Этот подход неэффективен для длинных строк из-за:

• Перебора всех возможных подстрок O(n²)
• Проверки каждой подстроки на палиндром O(n)

Принцип работы алгоритма Манакера

Алгоритм Манакера основан на двух ключевых идеях:

1. Предобработка строки путём вставки специальных символов (например, '#') между каждыми двумя символами и по краям. Это позволяет единообразно обрабатывать палиндромы как чётной, так и нечётной длины.

2. Использование симметрии палиндромов для ускорения вычислений. Если мы знаем, что некоторая подстрока является палиндромом с центром в позиции i, мы можем использовать эту информацию для определения палиндромов с центрами, симметричными относительно i.

Реализация алгоритма Манакера

Шаг 1: Предобработка строки

function preprocess(s) {
  let result = '#';
  for (let i = 0; i < s.length; i++) {
    result += s[i] + '#';
  }
  return result;
}

Например, строка "babad" превратится в "#b#a#b#a#d#".

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→

Шаг 2: Основной алгоритм Манакера

function manacher(s) {
  // Предобработка строки
  const processed = preprocess(s);
  const n = processed.length;
  
  // Массив для хранения радиусов палиндромов с центрами в каждой позиции
  const P = new Array(n).fill(0);
  
  // Переменные для отслеживания текущего центра палиндрома и его правой границы
  let C = 0;  // Центр текущего палиндрома
  let R = 0;  // Правая граница текущего палиндрома
  
  for (let i = 1; i < n - 1; i++) {
    // Если i находится в пределах правой границы, используем симметрию
    if (R > i) {
      // i' — зеркальное отражение i относительно C
      const mirror = 2 * C - i;
      // Начальное значение P[i] — минимум из расстояния до правой границы
      // и значения P для зеркальной позиции
      P[i] = Math.min(R - i, P[mirror]);
    }
    
    // Расширяем палиндром вокруг центра i
    while (i + P[i] + 1 < n && i - P[i] - 1 >= 0 && 
           processed[i + P[i] + 1] === processed[i - P[i] - 1]) {
      P[i]++;
    }
    
    // Если палиндром с центром в i выходит за правую границу R,
    // обновляем C и R
    if (i + P[i] > R) {
      C = i;
      R = i + P[i];
    }
  }
  
  // Находим максимальное значение в массиве P и его индекс
  let maxLen = 0;
  let centerIndex = 0;
  
  for (let i = 0; i < n; i++) {
    if (P[i] > maxLen) {
      maxLen = P[i];
      centerIndex = i;
    }
  }
  
  // Вычисляем начальный индекс самого длинного палиндрома в исходной строке
  const start = Math.floor((centerIndex - maxLen) / 2);
  
  // Возвращаем самый длинный палиндром
  return s.substring(start, start + maxLen);
}

Анализ алгоритма:

✅ Линейная временная сложность O(n)

✅ Линейная пространственная сложность O(n)

✅ Корректно обрабатывает палиндромы как чётной, так и нечётной длины

✅ Использует симметрию для оптимизации вычислений

Расширенные возможности алгоритма

Нахождение всех палиндромных подстрок

function findAllPalindromes(s) {
  const processed = preprocess(s);
  const n = processed.length;
  const P = new Array(n).fill(0);
  
  let C = 0;
  let R = 0;
  
  for (let i = 1; i < n - 1; i++) {
    if (R > i) {
      const mirror = 2 * C - i;
      P[i] = Math.min(R - i, P[mirror]);
    }
    
    while (i + P[i] + 1 < n && i - P[i] - 1 >= 0 && 
           processed[i + P[i] + 1] === processed[i - P[i] - 1]) {
      P[i]++;
    }
    
    if (i + P[i] > R) {
      C = i;
      R = i + P[i];
    }
  }
  
  // Собираем все уникальные палиндромы
  const palindromes = new Set();
  
  for (let i = 0; i < n; i++) {
    const center = i / 2; // Преобразуем индекс к исходной строке
    const radius = P[i] / 2; // Преобразуем радиус к исходной строке
    
    // Для каждого радиуса от максимального до 1
    for (let r = Math.floor(radius); r >= 1; r--) {
      const start = Math.ceil(center - r);
      const end = Math.floor(center + r);
      
      if (start >= 0 && end < s.length) {
        palindromes.add(s.substring(start, end + 1));
      }
    }
    
    // Обрабатываем палиндромы длины 1 (если центр попадает на символ)
    if (Number.isInteger(center) && center >= 0 && center < s.length) {
      palindromes.add(s[center]);
    }
  }
  
  return Array.from(palindromes);
}

Подсчёт числа палиндромных подстрок

function countPalindromicSubstrings(s) {
  const processed = preprocess(s);
  const n = processed.length;
  const P = new Array(n).fill(0);
  
  let C = 0;
  let R = 0;
  let count = 0;
  
  for (let i = 1; i < n - 1; i++) {
    if (R > i) {
      const mirror = 2 * C - i;
      P[i] = Math.min(R - i, P[mirror]);
    }
    
    while (i + P[i] + 1 < n && i - P[i] - 1 >= 0 && 
           processed[i + P[i] + 1] === processed[i - P[i] - 1]) {
      P[i]++;
    }
    
    if (i + P[i] > R) {
      C = i;
      R = i + P[i];
    }
    
    // Каждый радиус представляет собой уникальный палиндром
    count += Math.ceil(P[i] / 2);
  }
  
  return count;
}

Практические применения 🌟

1. Обработка текстов:

   • Поиск палиндромных фраз в больших текстах
   • Анализ стилистических особенностей литературных произведений

2. Биоинформатика:

   • Поиск палиндромных последовательностей в ДНК
   • Анализ симметричных структур в белках

3. Компрессия данных:

   • Использование палиндромных свойств для оптимизации сжатия

4. Проверка целостности данных:

   • Использование палиндромных свойств для обнаружения ошибок

Оптимизации и рекомендации 💡

1. Предобработка строки:

   • Можно использовать любой символ, не встречающийся в исходной строке, вместо '#'
   • В некоторых реализациях используются другие символы, например '$' и '^' в качестве ограничителей

2. Избегание выхода за границы:

   • Добавление ограничителей по краям строки помогает избежать проверок границ
   • Например, преобразование "abcba" в "^#a#b#c#b#a#$"

3. Оптимизация памяти:

   • Если нужен только самый длинный палиндром, можно хранить только его параметры
   • Для больших строк можно использовать более компактные типы данных

Сравнение с другими алгоритмами

Типичные ошибки при реализации

1. 🤦‍♂️ Неправильная обработка границ при расширении палиндрома
2. 😅 Путаница с индексами при преобразовании между исходной и предобработанной строкой
3. 🔄 Некорректное использование условия симметрии
4. 🧮 Ошибки при обработке палиндромов чётной и нечётной длины

Эффективная реализация

function efficientManacher(s) {
  if (!s || s.length === 0) return "";
  if (s.length === 1) return s;
  
  // Предобработка с использованием разных символов для границ
  function preprocess(s) {
    const n = s.length;
    if (n === 0) return "^$";
    
    let result = "^";
    for (let i = 0; i < n; i++) {
      result += "#" + s[i];
    }
    result += "#$";
    
    return result;
  }
  
  const T = preprocess(s);
  const n = T.length;
  const P = new Array(n).fill(0);
  
  let C = 0, R = 0;
  
  // Основной цикл алгоритма
  for (let i = 1; i < n - 1; i++) {
    const mirror = 2 * C - i; // Зеркальный индекс i относительно C
    
    // Используем информацию о зеркальном палиндроме
    if (R > i) {
      P[i] = Math.min(R - i, P[mirror]);
    }
    
    // Расширяем палиндром вокруг центра i
    while (T[i + 1 + P[i]] === T[i - 1 - P[i]]) {
      P[i]++;
    }
    
    // Если палиндром с центром в i расширяется за R,
    // обновляем C и R
    if (i + P[i] > R) {
      C = i;
      R = i + P[i];
    }
  }
  
  // Находим самый длинный палиндром
  let maxLen = 0;
  let centerIndex = 0;
  
  for (let i = 1; i < n - 1; i++) {
    if (P[i] > maxLen) {
      maxLen = P[i];
      centerIndex = i;
    }
  }
  
  // Преобразуем индексы обратно к исходной строке
  const start = Math.floor((centerIndex - 1 - maxLen) / 2);
  
  return s.substring(start, start + maxLen);
}

Заключение

Алгоритм Манакера представляет собой:

• ⚡ Элегантное решение классической задачи поиска палиндромов
• 🧠 Пример эффективного использования свойств симметрии
• 🔍 Демонстрацию оптимизации от O(n³) до O(n)
• 🌟 Важный инструмент в арсенале алгоритмов обработки строк

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