Строки

← →
Александр из Минска (2003-12-15 15:26) [0]

Подскажите алгоритм (или что-нибудь из стандартных функций) для определения схожести двух строк. Например,
s1 := "11011";
s2 := "0011";
После вычислений дожно вывести максимальную схожую строку ("11").

← →
Семен Сорокин (2003-12-15 15:31) [1]

а если строки такие:
s1 := "110011";
s2 := "0011";
как будет выглядеть "максимальная схожая строка"?

← →
Александр из Минска (2003-12-15 15:33) [2]

Это уже не важно, так как мне нужна длина этой макс. строки...

← →
REA (2003-12-15 15:34) [3]

> После вычислений дожно вывести максимальную схожую строку
> ("11").

А почему не 011?

← →
Romkin (2003-12-15 15:40) [4]

Максимальная общая строка из двух? Есть такой алгоритм :) Смотри динамическое программирование, вроде там. Это один из канонических примеров, попробуй поискать "максимальная подпоследовательность"

← →
Александр из Минска (2003-12-15 15:41) [5]

Прошу прощения, должно быть 011...

← →
Romkin (2003-12-15 15:42) [6]

Ну да, как я и сказал http://algolist.manual.ru/search/lcs/index.php

← →
Александр из Минска (2003-12-15 15:45) [7]

Всем спасибо, сейчас опробую :)

Строки Найти похожие ветки