|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Pertzel Family 2:5020/400 03 Jul 2002 03:05:09
To : Daniil Uspensky
Subject : Re: Поиск наилучшего (а также неполного) вхождения подстроки в строку
--------------------------------------------------------------------------------
> Hапример имеется строка abcabacbcabacbbbca, в которой мы ищем подстроку
> bcabacba
> Hаилучшим вхождением будет 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)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Re: Поиск наилучшего (а также неполного) вхождения подстроки в строку