Mercury13

1. Каким-то образом преобразовать обе строки, чтобы избавиться от расхождений по стартовым слэшам. Слишком мало информации, КАК это сделать — возможна ситуация, когда вторая строка не начинается со слэша, а первая нет, но бывают ли другие?
2. Убедиться, что вторая строка — префикс первой. Если нет — непонятно, что делать.
3. Если вторая строка непуста и не кончается слэшом, убедиться, что в первой на этом месте слэш. Пропустить его.
4.1. Если от первой строки ничего не осталось — если в конце слэш, пропустить, и извлечь кусок до следующего с конца слэша.
4.2. А если осталось — извлечь кусок до слэша.
5. Придумай методику хранения информации. Вероятно, выделить память? — тогда на каждый результат придётся давать free.

Если f(n) ≡ 0 (неотрицальна → асимптотически неотрицательна), то вполне срабатывает, что 0=Θ(0).
То есть по нашему определению множества Θ, если оно непустое, то g обязана быть асимптотически неотрицательной — но не обязательно асимптотически положительной.

Вот разбор строки.


Совместимая декомпозиция NFKD (а лучше совместимая композиция NFKC) конкретно тут не поможет (не меняет ни одного символа), но в других случаях может улучшить жизнь.

Затем тебе придётся работать с визуально сходными символами, и начинать надо отсюда.
https://util.unicode.org/UnicodeJsps/confusables.jsp



Этого тоже мало, но вот с этого начинать надо.

У нас два вложенных цикла, каждый порядка n.
Значит, O(n)·O(n) = O(n²), если не докажем меньше.
Не докажем, там обычная арифметическая прогрессия, которая что-то вроде n(n—1)/2.

Как я понял, робот смотрит вниз.
Поверни вправо. Подумай, как надо двигаться, чтобы разрушить четыре блока, стоять в 3-й строке, 2-м столбце и смотреть вниз. Повтори четырежды.

Изначально:
1. У корня глубина 0.

Команда ADD:
1. вершина.предок = предок
2. вершина.глубина = предок.глубина + 1

Команда GET:
1. Найти ту вершину, что глубже. Если у одной глубина 5, у другой 7 — подняться от второй на 2.
2. А теперь параллельно и от первой, и от второй вершины поднимаемся вверх на единицу, пока не придём в одну и ту же вершину.

Если хватит памяти — можно устроить какой-то кэш. Мой вариант — кэшировать предков порядка 1,2,4,8…
Чтобы подняться от вершины на 30 единиц…
1. Находим ближайшую степень двойки (16).
2. Если эта степень есть в кэше — просто берём её.
3. Иначе находим максимальную имеющуюся степень (например, 4). Заходим в эту вершину и рекурсивно поднимаемся от неё на 4, потом на 8, заполняя наш кэш.
4. На оставшиеся 14 поднимаемся по тому же алгоритму.

Чтобы найти общего предка двух вершин — у одной глубина 30, у другой 40.
1. От той вершины, у которой 40, поднимаемся на 10 единиц. Алгоритм я привёл.
2. Одинаковые? — тогда понятно.
3. Имеют общего предка? — тогда понятно.
4. Иначе поднимаемся на 1, 2, 4, 8, 16 единиц от каждой из них по указанному алгоритму, каждый из этих шагов при наличии кэша даст O(1). Находим последнюю НЕСОВПАДАЮЩУЮ глубину. Для них повторяем алгоритм.

ВАРИАНТ КЭША ВТОРОЙ. Для вершины глубины 27=11010 кэшировать предков АБСОЛЮТНЫХ (то есть от корня!) глубин 16=1.0000, 24=11.000, 24 :) =110.00, 26=1101.0. Тогда при создании вершины весь кэш достаточно быстро строится на основе кэша вершины-предка.

Чтобы подняться от вершины глубины 27 на расстояние, например, 5, нам нужна абсолютная глубина 27−5=22.
Есть только 24 → действуем так. Выныриваем туда на 24, но там кэш совершенно негодный → а дальше нас проведёт кэш глубины 23. Так поднимаемся на 1 до 23-й и повторяем алгоритм.

Чтобы найти общего предка двух вершин (их глубины, скажем, 27 и 42), точно так же уравниваем глубины. Затем поднимаемся до глубин 16, 24, 24, 26…, пока не найдём несовпадение. Идём в эти несовпадающие вершины, проходим от них к предку и повторяем алгоритм.

L → EZUU M ZUUUUF
M → ZUU M ZUUUU | S
Для S грамматику вы уже придумали.
Затем — не буду расписывать, они многословны, но просты — UZ → ZU

А чтобы превратить Z в 0 и U в единицу, если i,n ∊ N+…
Сделаем затравку…
EZ → E0
Ua → 1a
cZ → c0
UF → 1F
…Уничтожим технические нетерминалы…
E0 → 0
1F → 1
…И проведём волну!
0Z → 00
U1 → 11

Вроде так.
(Z = zero, U = unit)

Это называется кластеризация, и самый ходовой метод для неё — K-means.

H = |haystack|, n = |needle|, a — размер алфавита.
Примитивный алгоритм: предобработки нет, работа в среднем 2H, максимум O(Hn).
Типичные быстрые алгоритмы: предобработка O(n) или O(n+a), работа в среднем <H, максимум O(Hn).
Автоматные алгоритмы: предобработка O(na) или O(n+a), работа =H.
Существуют СТРАШНЫЕ алгоритмы с работой в среднем <H и максимум O(H), где применяются — не знаю.
Если нужно проводить несколько поисков одной «иголки» в разных «стогах», нужна всего одна предобработка.

Будут повторы?
Если не будет — то достаточно отсортировать char’ы и использовать числовой алгоритм.
Если будут — ищите «размещения с повторами», и тоже сортируйте.

1. Нечто, действительно имеющее древовидную форму — например, деревья каталогов на дисках, деревья сцен в 3D, деревья принятия решений.
2. Деревья поиска — структуры данных, позволяющие добавлять-убирать объекты и позволяющие быстрый поиск по ключу. Например, словари всякие, индексы БД.
3. Так называемая куча — структура данных, позволяющая добавлять-убирать объекты и поддерживающая минимальный элемент в этом множестве. Используется как вспомогательная в каких-нибудь алгоритмах.
4. Двоичное разбиение пространства в 3D — известный способ сортировки от дальних к ближним.

Кроме того, деревья могут не существовать в памяти, а только подразумеваться — в синтаксических разборах, теоретико-игровых обсчётах. Хотя один из вариантов промежуточного хранения разобранной формулы, чтобы потом по ней проводить многократные расчёты — дерево (но чаще используют обратную польскую запись).