поиск строки случайных символов (с возможными ошибками) в большой строке случайных символов

Question

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

Я нашел способ найти строку, если нет лишних символов, используя indexOf (string.charAt (0)) и indexOf (charAt (string.length () - 1) и циклически перебирая символы между двумя индексами. но это может быть проблематично при работе со случайными символами из-за возможности найти первый и последний символы в правильном интервале, но ни один из средних символов не совпадает.

Я часами чесал голову по этому вопросу. есть идеи?

Answer 1

Вот статья Я обнаружил, что показывает, как будет работать простая проверка орфографии. Я знаю, что вы не проверяете орфографию, но идеи будут похожи.

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

Answer 2

То, что вы пытаетесь сделать, во многом похоже на тип сопоставления строк, который биоинформатики сопоставляют последовательности ДНК и тому подобное. Это идет под термином выравнивание последовательности .

Answer 3

Если предположить, что ваша строка поиска имеет длину, скажем, 6 символов, а первый и последний символы - "A" и "Z", то

A.{4}Z

будет соответствовать любой подстроке в большей строке, где первый и последний символы совпадают в правильном интервале.

Это то, что тебе нужно?