Оптимизация поиска палиндрома

Преобразую код

Предлагаю переписать код на C++, внести изменения в переменные и функции, оптимизировать, добавив краткие комментарии на русском языке, следуя стилю Google Code и отступам в два пробела.

Реализуя обработку

Сначала создаю функции для нахождения максимума и длины строки. Затем, в функции main, считываю строку и передаю её в LengthPalindrom.

Создание и вычисление

Сначала код создает массив char и обращает строку. Затем применяет динамическое программирование для нахождения длины самого длинного палиндромного подстроки.

Определяю задачи

Считаю длину самого длинного палиндромного подпоследовательности и нахожу минимальное количество вставок или удалений для превращения строки в палиндром.

Изменение названий

Переименовываю функции и переменные, чтобы лучше отражать их назначение, включая вычисление минимальных вставок для создания палиндрома.

Изменяю функции и переменные, чтобы более понятно ввести строки и перевернутые строки, и вычислить минимальные добавления для палиндрома.

Определяю левси-жемчужину

Уточняю детали

Я думаю о оптимизации функции StringLength, предложенной участником, используя двухмерный массив для хранения и переноса вычислений длины строки.

Формирование строки

Пишу функцию StringLength, чтобы подсчитать длину строки, пока не достигну символа null.

Создание обратной строки

Использую ComputeLCSLength, чтобы вычислить длину самого длинного общей подпоследовательности (LCS) между строкой и её обратной версией, применяя метод динамического программирования.

Упрощение алгоритма

Я думаю о том, чтобы оптимизировать динамическое программирование, используя только две строки в двумерном массиве [2][len+1]. Поменяю имена переменных и добавлю важные комментарии на русском.

Инициализация массивов

Я начинаю с выделения памяти для массивов prev и curr, которые используются для хранения длин подстрок. Затем инициализирую их нулями.

Переименование и добавление объяснений

Вместо str1 и str2 предлагаю использовать s и t. Добавляю комментарии на русском в важных местах.

Сейчас я работаю над функцией Max для поиска максимума двух чисел, затем перехожу в функцию ComputeLCSLength для анализа двух строк и нахождения их общей подпоследовательности.

Оптимизация памяти

Обновляю код для минимальных вставок в палиндром, уменьшив использование памяти и улучшив читаемость.

Проверяю код

Проверяю корректность кода, меняя местами указатели prev и curr, а затем добавляю комментарии на русском языке.

Находим длину самой длинной общей подпоследовательности

Функция ComputeLCSLength использует динамическое программирование, чтобы определить длину самой длинной общей подпоследовательности между двумя строками. Затем, функция PrintMinInsertionsToPalindrome вычисляет минимальное количество вставок для превращения строки в палиндром, используя обратную строку и ту же функцию LCS.

Проверка стиля

Я уточняю стиль C++ для соответствия Google, включая названия функций и переменных, в документации.

Переименование переменных

Переменные переименованы в lowerCamelCase, и функции следует привести к этому стилю.

Определяю максимальное

Сначала я выявляю функцию max, затем stringLength для длины строки, а затем computeLcsLength для нахождения длины самого длинного общего подпоследовательности (LCS) двух строк с использованием динамического программирования.

#include <iostream>

int max(int a, int b) {
  return (a > b) ? a : b;
}

int stringLength(const char* str) {
  int len = 0;
  // Вычисляем длину строки
  while (str[len] != '\0') {
    ++len;
  }
  return len;
}

int computeLcsLength(const char* str1, const char* str2, int len) {
  int* prev = new int[len + 1];
  int* curr = new int[len + 1];

  // Инициализируем предыдущую строку нулями
  for (int j = 0; j <= len; ++j) {
    prev[j] = 0;
  }

  // Запускаем динамическое программирование
  for (int i = 1; i <= len; ++i) {
    curr[0] = 0;
    for (int j = 1; j <= len; ++j) {
      if (str1[i - 1] == str2[j - 1]) {
        // Если символы совпадают, увеличиваем длину подпоследовательности
        curr[j] = prev[j - 1] + 1;
      } else {
        // Иначе берем максимальное значение из соседних клеток
        curr[j] = max(prev[j], curr[j - 1]);
      }
    }
    // Обмениваем текущую и предыдущую строки
    int* temp = prev;
    prev = curr;
    curr = temp;
  }

  int lcsLength = prev[len];

  delete[] prev;
  delete[] curr;

  return lcsLength;
}

void printMinInsertionsToPalindrome(char* str) {
  int len = stringLength(str);
  char* reversedStr = new char[len + 1];
  // Создаем перевернутую строку
  for (int i = 0; i < len; ++i) {
    reversedStr[i] = str[len - i - 1];
  }
  reversedStr[len] = '\0';
  // Вычисляем длину наибольшей общей подпоследовательности между строкой и ее реверсом
  int lcsLength = computeLcsLength(str, reversedStr, len);
  // Выводим минимальное количество вставок для палиндрома
  std::cout << (len - lcsLength);
  delete[] reversedStr;
}

int main() {
  char inputStr[10000] = "";
  std::cin >> inputStr;
  // Вычисляем и выводим минимальное количество вставок для получения палиндрома
  printMinInsertionsToPalindrome(inputStr);
  return 0;
}

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

Преобразование и оптимизация кода

Рассматриваю код и замечаю оператор териарного делания, который хотел бы переписать, избегая его в дальнейшем.

Ищем длинный лсс

В коде я нахожу максимальное значение длины общей подпоследовательности строк и определяю минимальное количество вставок для превращения в палиндром.

Использование инофункций

Я переключаюсь на использование функций if-else вместо тернарных операторов для оптимизации кода, снимая это дуально.

Определяю длину последовательности

Создаю алгоритм нахождения наибольшей общей подпоследовательности (LCS) двух строк и нахожу минимальное количество вставок для превращения строки в палиндром.

#include <iostream>

int max(int a, int b) {
  if (a > b) {
    return a;
  } else {
    return b;
  }
}

int stringLength(const char* str) {
  int len = 0;
  // Вычисляем длину строки
  while (str[len] != '\0') {
    ++len;
  }
  return len;
}

int computeLcsLength(const char* str1, const char* str2, int len) {
  int* prev = new int[len + 1];
  int* curr = new int[len + 1];

  // Инициализируем предыдущую строку нулями
  for (int j = 0; j <= len; ++j) {
    prev[j] = 0;
  }

  // Запускаем динамическое программирование
  for (int i = 1; i <= len; ++i) {
    curr[0] = 0;
    for (int j = 1; j <= len; ++j) {
      if (str1[i - 1] == str2[j - 1]) {
        // Если символы совпадают, увеличиваем длину подпоследовательности
        curr[j] = prev[j - 1] + 1;
      } else {
        // Иначе берем максимальное значение из соседних клеток
        curr[j] = max(prev[j], curr[j - 1]);
      }
    }
    // Обмениваем текущую и предыдущую строки
    int* temp = prev;
    prev = curr;
    curr = temp;
  }

  int lcsLength = prev[len];

  delete[] prev;
  delete[] curr;

  return lcsLength;
}

void printMinInsertionsToPalindrome(char* str) {
  int len = stringLength(str);
  char* reversedStr = new char[len + 1];
  // Создаем перевернутую строку
  for (int i = 0; i < len; ++i) {
    reversedStr[i] = str[len - i - 1];
  }
  reversedStr[len] = '\0';
  // Вычисляем длину наибольшей общей подпоследовательности между строкой и ее реверсом
  int lcsLength = computeLcsLength(str, reversedStr, len);
  // Выводим минимальное количество вставок для палиндрома
  std::cout << (len - lcsLength);
  delete[] reversedStr;
}

int main() {
  char inputStr[10000] = "";
  std::cin >> inputStr;
  // Вычисляем и выводим минимальное количество вставок для получения палиндрома
  printMinInsertionsToPalindrome(inputStr);
  return 0;
}

Я переписал функцию max без использования тернарного оператора, заменив его на обычную конструкцию if-else. Остальной код остался без изменений, и в нем не используются тернарные операторы.