Re: Поиск наилучшего (а также неполного) вхождения подстроки в строку

From

Pertzel Family ()

To

Daniil Uspensky

Date

2002-07-03T03:05:09Z

Area

RU.ALGORITHMS

From: "Pertzel Family" <voldemar@relhum.org>

> Например имеется строка abcabacbcabacbbbca, в которой мы ищем подстроку
> bcabacba
> Наилучшим вхождением будет bcabacb. Или еще можно ввести "достаточное"
> совпадение, т.е. если наилучшее слишком трудоемко искать, то ограничиться
> поискаом первого достаточного.

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

0 - пустой строке
1 - b
2 - bc
3 - bca
4 - bcab
5 - bcaba
6 - bcabac
7 - bcabacb

из 0-й в 1-ю будет вести только буква b, все остальные - в 0-ю,
сл-но, в таблице в 0-й сьрокке будут все ноли, и только одна
единица на месте ascii('b').
из 1-й во 1-ю будет вести только буква b, во 2-ю будет вести
только буква с, все остальные - в 0-ю...
.......
из 4-й в 1-ю будет вести только буква b, во 2-ю будет вести
только буква с, в 5-ю будет вести только буква a, все
остальные - в 0-ю...
........


В момент достижения позиции с максимальным доселе виденным
номером, перезапоминаешь место и номер, они будут соответствовать
концу и длине подстроки.

--- ifmail v.2.15dev5
 * Origin: Sent via Graf's Inn at news://news.relhum.org (2:5020/400)