Проверка симметричности строки

Задача

Дана строка. Нужно определить, являются ли её две половины одинаковыми (симметричными).

Если длина строки чётная, строки делятся пополам. Если нечётная — средний символ игнорируется и сравниваются оставшиеся половины.

Примеры

1. str = “abab”

   Левая половина = “ab”, правая = “ab” → симметрично.

   Вывод: “Да, строка симметрична”.

2. str = “madam”

   Длина нечётная, средний символ ‘d’ игнорируется: первая половина = “ma”, вторая = “am” → не совпадают.

   Вывод: “Нет, строка не симметрична”.

3. str = “madma”

   Первая половина = “ma”, вторая = “ma” → совпадают.

   Вывод: “Да, строка симметрична”.

Алгоритм двумя указателями

Краткая последовательность действий:

1. Найти длину строки length.
2. Вычислить midIndex:
   • если length чётно, midIndex = length / 2;
   • если length нечётно, midIndex = length / 2 + 1 (средний символ пропускается).
3. Инициализировать pointer1 = 0 и pointer2 = midIndex.
4. Пока pointer1 < midIndex и pointer2 < length:
   • если str[pointer1] != str[pointer2], вернуть false;
   • иначе увеличить pointer1 и pointer2.
5. Если цикл завершился без различий, вернуть true.

Пояснение: этот алгоритм сравнивает i-й символ левой половины с соответствующим символом правой половины. Работает за O(n) времени и O(1) памяти.

C++ Пример

// C++ программа для проверки симметричности строки
#include 
#include 
using namespace std;

bool isSymmetrical(const string& str) {
    int length = str.length();
    int midIndex;
    if (length % 2 == 0) {
        midIndex = length / 2;
    } else {
        midIndex = length / 2 + 1; // пропускаем средний символ
    }
    int pointer1 = 0;
    int pointer2 = midIndex;
    while (pointer1 < midIndex && pointer2 < length) {
        if (str[pointer1] == str[pointer2]) {
            pointer1 += 1;
            pointer2 += 1;
        } else {
            return false;
        }
    }
    return true;
}

int main() {
    string str1 = "abab";
    cout << "String 1: " << str1 << endl;
    if (isSymmetrical(str1)) cout << "Да, строка симметрична" << endl; else cout << "Нет, строка не симметрична" << endl;

    string str2 = "madam";
    cout << "String 2: " << str2 << endl;
    if (isSymmetrical(str2)) cout << "Да, строка симметрична" << endl; else cout << "Нет, строка не симметрична" << endl;

    string str3 = "madma";
    cout << "String 3: " << str3 << endl;
    if (isSymmetrical(str3)) cout << "Да, строка симметрична" << endl; else cout << "Нет, строка не симметрична" << endl;

    string str4 = "civic";
    cout << "String 4: " << str4 << endl;
    if (isSymmetrical(str4)) cout << "Да, строка симметрична" << endl; else cout << "Нет, строка не симметрична" << endl;

    string str5 = "khokho";
    cout << "String 5: " << str5 << endl;
    if (isSymmetrical(str5)) cout << "Да, строка симметрична" << endl; else cout << "Нет, строка не симметрична" << endl;

    return 0;
}

Пример вывода:

String 1: abab
Да, строка симметрична
String 2: madam
Нет, строка не симметрична
String 3: madma
Да, строка симметрична
String 4: civic
Нет, строка не симметрична
String 5: khokho
Да, строка симметрична

Python Пример

# Python программа для проверки симметричности строки

def is_symmetrical(s):
    length = len(s)
    if length % 2 == 0:
        mid_index = length // 2
    else:
        mid_index = length // 2 + 1  # пропускаем средний символ

    pointer1 = 0
    pointer2 = mid_index

    while pointer1 < mid_index and pointer2 < length:
        if s[pointer1] == s[pointer2]:
            pointer1 += 1
            pointer2 += 1
        else:
            return False
    return True

# Тесты
for s in ["abab", "madam", "madma", "civic", "khokho"]:
    print("String:", s)
    print("Да, строка симметрична" if is_symmetrical(s) else "Нет, строка не симметрична")

Вывод будет аналогичен примеру для C++.

JavaScript Пример

// JavaScript программа для проверки симметричности строки
function isSymmetrical(str) {
  var length = str.length;
  var midIndex;
  if (length % 2 === 0) {
    midIndex = Math.floor(length / 2);
  } else {
    midIndex = Math.floor(length / 2) + 1; // пропускаем средний символ
  }
  var pointer1 = 0;
  var pointer2 = midIndex;
  while (pointer1 < midIndex && pointer2 < length) {
    if (str[pointer1] === str[pointer2]) {
      pointer1 += 1;
      pointer2 += 1;
    } else {
      return false;
    }
  }
  return true;
}

let tests = ["abab", "madam", "madma", "civic", "khokho"];
for (let s of tests) {
  console.log("String:", s);
  console.log(isSymmetrical(s) ? "Да, строка симметрична" : "Нет, строка не симметрична");
}

Когда подход даёт неверный результат

• Если требуется учитывать регистр, но вы не нормализовали строки: “Aa” и “aa” считаются разными. Решение: привести к одному регистру (toLowerCase / tolower).
• Если нужно игнорировать пробелы и знаки препинания, текущая логика их учитывает. Решение: предварительно удалить нежелательные символы.
• Алгоритм не проверяет палиндромность (слово читается одинаково в обе стороны). Симметричность по половинам — другое свойство.

Примеры ошибок:

• “AbaA” при нечувствительном к регистру сравнении может быть симметрично, а при чувствительном — нет.
• Строки с UTF-8 символами (комбинирующие акценты) могут требовать нормализации (NFC/NFD).

Альтернативные подходы

1. Срезы и сравнение (удобно в Python): сравнить s[:n//2] и s[-n//2:]. Простой и читаемый подход.
2. Копирование и сравнение: создать правую половину через substring и сравнить через ==. Простая реализация, O(n) по времени и O(n) по памяти.
3. Хеширование: вычислить хеш для левой и правой половин и сравнить. Быстрее при многократных проверках одних и тех же подстрок, но сложнее и требует аккуратного выбора хеш-функции.
4. SIMD/векторизация на уровне С/C++ для длинных строк в производительных системах.

Когда выбирать:

• Для читаемости и небольших строк — срезы (Python) или substring.
• Для ограниченной памяти — метод с двумя указателями O(1) памяти.
• Для больших объёмов проверок — хеширование или предкомпьютирование префиксных хешей.

Эвристика и ментальные модели

• Подумайте о строке как о ленте, которую делят пополам; сравниваются соответствующие «ячейки».
• Для нечётной длины средний элемент — мост, который не участвует в сравнении.
• Если вы видите задачу про «симметрию половин», не путайте с палиндромом.

Критерии приёмки

• Функция корректно обрабатывает пустую строку (считайте её симметричной).
• Правильно работает для чётной и нечётной длины.
• Поддерживает строки с Unicode (если это требование проекта).
• Для опциональной нормализации (регистр, пробелы) — поведение документировано и покрыто тестами.

Тестовые случаи

1. Пустая строка: “” → true
2. Чётная симметричная: “abab” → true
3. Нечётная несимметричная: “madam” → false
4. Нечётная симметричная: “madma” → true
5. Регистронезависимый случай: “AaAa” при нормализации → true
6. Unicode с комбинирующими символами — проверить после нормализации

Краткий глоссарий

• Симметричность: равенство левой и правой половин строки.
• Палиндром: строка, читающаяся одинаково слева направо и справа налево.
• midIndex: индекс начала правой половины (с учётом нечётной длины).

Резюме

• Алгоритм с двумя указателями даёт O(n) по времени и O(1) по памяти и подходит для большинства задач.
• Для специфичных требований (регистр, пробелы, Unicode) нужно предварительно нормализовать вход.
• В статье приведены рабочие реализации на C++, Python и JavaScript и набор тестов для приёмки.

Важно: перед массовой обработкой текстов убедитесь в требуемой нормализации и в необходимости чувствительности к регистру или пробелам.