Пошук співпадаючих і різних подстрок в двох рядках, наведених до загальної довжини. Результат - таблиця значень з №№ почав і закінчень однакових і різних фрагментів. Дихотомический обхід, висока швидкість.
Знадобилося мені 2 рядки порівняти і визначити, які в них фрагменти збігаються, а які розрізняються. Для зручності привів рядки до однієї довжині. Втім, при бажанні будь-які 2 рядки можна порубати так, щоб порівнювати як що мають однакову довжину. Ну і нічого, крім хитрих регулярних виразів та посимвольного перебору не знайшов. RegExp не вдалося пріпахать до видачі результату в потрібному мені вигляді (можливо, мої руки криві), а посимвольний обходити довгі рядки не хотілося. У підсумку зробив цю, авось кому стане в нагоді.
Функція ПолучітьРазлічіяДвухСтрок (Знач стро1, Знач стро2. Тф = Не визначено, Знач рДельта = 0)
Якщо тф = Не визначено Тоді
// це перша ітерація, ініціалізувавши
// результати повернемо в таблиці значень, що фіксує фрагменти: № начсім, № Консу, ЕстьРазніца (булево)
тф = Новий ТабліцаЗначеній;
тф. Колонки. Додати ( "Початок");
тф. Колонки. Додати ( "Кінець");
тф. Колонки. Додати ( "ЕстьРазніца");
Якщо стро1 = стро2 Тоді // різниці взагалі немає
стротф = тф. Додати ();
стротф. Початок = 1;
стротф. Кінець = СтрДліна (стро2);
рДліна1 = СтрДліна (стро1);
рДліна2 = СтрДліна (стро2);
якщо рДліна1 <> рДліна2 Тоді // можна обрізати під одну довжину, можна і відмовитися
рМінДліна = Мін (рДліна1. рДліна2);
рМаксДліна = Макс (рДліна1. рДліна2);
Якщо рМінДліна = рДліна1 Тоді стро2 = Лев (стро2. РМінДліна) КонецЕсли;
Якщо рМінДліна = рДліна2 Тоді стро1 = Лев (стро1. РМінДліна) КонецЕсли;
ПолучітьРазлічіяДвухСтрок (стро1. Стро2. Тф);
// дообработаем різницю довжин, якщо вона була, дописавши "хвіст" більш довгого рядка
якщо рМаксДліна <> 0 Тоді
стротф = тф. Додати ();
стротф. Початок = рМінДліна + 1;
стротф. Кінець = рМаксДліна;
стротф. ЕстьРазніца = Істина; // апріорно
// грубо звернемо (така таблиця ніколи не буде дуже великий, тому можна не викручуватись)
ТФ2 = тф. СкопіроватьКолонкі (); старЕР = Не визначено; старНачало = 0; старКонец = 0;
Для кожного стротф З тф Цикл
якщо старЕР <> стротф. ЕстьРазніца Тоді
якщо старЕР <>Не визначено Тоді // закінчимо попередню
стротф2 = ТФ2. Додати ();
стротф2. Початок = старНачало;
стротф2. Кінець = старКонец;
стротф2. ЕстьРазніца = старЕР;
старЕР = стротф. Є різниця ;
старНачало = стротф. Початок ;
старКонец = стротф. кінець;
якщо старЕР <>Не визначено Тоді // закінчимо попередню
стротф2 = ТФ2. Додати ();
стротф2. Початок = старНачало;
стротф2. Кінець = старКонец;
стротф2. ЕстьРазніца = старЕР;
// власне рекурсивне порівняння рядків
етстро = стро1; // рядок-еталон
обрстро = стро2; // обробляється рядок
пози = Цілий (СтрДліна (обрстро) / 2);
Якщо пози = 0 Тоді Повернення "" КонецЕсли; // ненормальна ситуація
кусет1 = Лев (етстро. пози);
кусет2 = Серед (етстро. пози + 1);
кусобр1 = Лев (обрстро. пози);
кусобр2 = Серед (обрстро. пози + 1);
ізм1 = (кусет1 <> кусобр1);
ізм2 = (кусет2 <> кусобр2);
// дивимося перший шматок
Якщо не ізм1 Тоді
стротф = тф. Додати ();
стротф. Початок =? (РДельта = 0. 1. рДельта);
стротф. Кінець = стротф. Початок + СтрДліна (кусобр1) - 1;
стротф. ЕстьРазніца = Брехня;
Інакше // ця частина різна, йдемо далі, обробляючи її як окремий рядок
рНачало =? (рДельта = 0. 1. рДельта);
рКонец = рНачало + СтрДліна (кусобр1) - 1;
Якщо рНачало = рКонец Тоді // фінальна фаза, 1 символ різниці
стротф = тф. Додати ();
стротф. Початок = рНачало;
стротф. Кінець = рКонец;
стротф. ЕстьРазніца = Істина;
ПолучітьРазлічіяДвухСтрок (кусет1. Кусобр1. Тф. РДельта);
// дивимося другий шматок
рДельта = (пози + 1) + рДельта -? (рДельта = 0. 0. 1);
Якщо не ізм2 Тоді
стротф = тф. Додати ();
стротф. Початок = рДельта;
стротф. Кінець = стротф. Початок + СтрДліна (кусобр2) - 1;
стротф. ЕстьРазніца = Брехня;
Інакше // ця частина різна, йдемо далі, обробляючи її як окремий рядок
рКонец = рНачало + СтрДліна (кусобр2) - 1;
Якщо рНачало = рКонец Тоді // фінальна фаза, 1 символ різниці
стротф = тф. Додати ();
стротф. Початок = рНачало;
стротф. Кінець = рКонец;
стротф. ЕстьРазніца = Істина;
ПолучітьРазлічіяДвухСтрок (кусет2. Кусобр2. Тф. РДельта);
// нічого не повертаємо, результат не важливий