@lena_tihonova_bl
М-да… звучит, как олимпиадная задача из шкилы, но мне правда нужно это как-то решить… Помогите, пожалуйста. Если есть вопросы — готов ответить.
P.S. В целом, я, скорее всего, быстро смогу сделать так, чтобы программа не обращала внимания на погрешности. Основной вопрос именно в нахождении части для обрезания, так как строки не буквально одинаковые, а с погрешностями.
Решения вопроса 1
@sergiks
Предлагаю прокатиться одной строкой вдоль второй.
_________zzzoooABCuuu
xxxABCiii |||
xxxABCiii |||
xxxABCiii |||
... |||
xxxABCiii
...
xxxABCiii
Начать ещё до их пересечения – это максимально возможное их несовпадение.
И сдвигать по одной позиции вправо.
Сравнивать, считая ошибки: количество не совпавших позиций.
Взять тот сдвиг, где ошибок минимум.
С «минимальными отличиями» пока не придумал ничего толкового. В этом коде просто предполагаю, что единично-отличные символы находятся не с краю совпадающих строк. Иначе всегда можно присобачить по 1 лишнему символу в начале и в конце, заявив, что именно они в этот раз случайно оказались разными )
function mostCommon(a, b) {
const A = a.split('');
const B = b.split('');
const min = {
diff: A.length + B.length,
index: -A.length,
start: undefined,
finish: undefined,
};
for (let offset = -A.length; offset < B.length; offset++) {
let diff = Math.max(0, -offset) + Math.max(offset + A.length - B.length, 0);
const initialDiff = Math.max(0, -offset) + Math.max(offset + A.length - B.length, 0);
const start = Math.min(Math.max(0, offset), B.length);
const finish = Math.min(Math.max(0, offset + A.length), B.length);
let matchStart;
let matchFinish;
for (let i = start, isMatchStarted = false; i < finish; i++) {
if (B[i] !== A[i - offset]) diff++;
else {
if (!isMatchStarted) {
matchStart = i;
isMatchStarted = true;
}
matchFinish = i;
}
}
if (diff < min.diff) {
min.diff = diff;
min.index = offset;
min.start = matchStart;
min.finish = matchFinish;
}
}
console.log(min, b.substring(min.start, min.finish + 1));
return min;
}
mostCommon('xxx>abcABCxxx', 'bbbzzz>abcAXCiiiqqq');
// { diff: 7, index: 3, start: 6, finish: 12 } >abcAXC
На примере из вопроса:
mostCommon("1246380924534", "88899212465809");
// { diff: 6, index: 6, start: 6, finish: 13 } 12465809
Ответы на вопрос 1
@rPman
Для не строгого сравнения строк придумали кучу алгоритмов, например Levenshtein, готовые реализации есть для кучи языков, гугли есть и для javascript. По факту это количество изменений, которые нужно сделать с первой строкой, чтобы превратить ее во вторую.
В некоторых реализациях (например на php) вводят разную оценку на разные действия типа вставки, замены и удаления. Т.е. если сделать стоимость вставки и удаления сильно меньше замены, возможно ты получишь желаемое.. или модифицировать алгоритм до своих хотелок.
p.s. суффиксное дерево, смотри там пример использования для поиска подстроки, это если у тебя БОЛЬШИЕ строки, эта структура поможет решать задачи похожие на твою