вняно з довжиною зразка, як це часто має місце з
function bmsearch (startpos: integer; const s, p: string;
const bmt: tbmtable): integer;
var
pos, lp, i: integer;
begin
lp: = length (p);
pos: = startpos + lp -1;
while pos if p [lp] <> s [pos] then pos: = pos + bmt [s [pos]]
else for i: = lp - 1 downto 1 do
if p [i] <> s [pos - lp + i] then
begin
inc (pos);
break;
end
else if i = 1 then
begin
result: = pos - lp + 1;
exit;
end;
result: = 0;
end;
p> таблицею ASCII і при звичайному пошуку в текстовому редакторі, він стає надзвичайно корисний. Використання в алгоритмі тільки його одного може бути досить ефективним. p> Після спроби суміщення x і y [i, i + m-1], довжина зсуву - не менше 1. Таким чином, символ y [I + m] обов'язково буде залучений у наступну спробу, а значить, може бути використаний в поточній спробі для зрушення поганого символу. Модифікуємо функцію поганого символу, щоб прийняти в розрахунок останній символ х:
bc [a] = min {j | 0 j m і x [m - 1 - j ] = A}, якщо a зустрічається в x,
bc [a] = m в протилежному випадку.
Порівняння тексту і зразка можуть проводитися в будь-якому порядку. p>
Лістинг 6
Турбо БМ (Класифікація Thierry Lecroq [2] ). br/>
Турбо - БМ є також є поліпшенням алгоритму Боуер - Мура. Ми будемо запам'ятовувати сегмент тексту, який зійшовся з суфіксом зразка під час минулої спроби (і тільки, якщо стався зсув хорошого суфікса).
Це дасть нам два переваги: ​​
1. Можливість перескочити через цей сегмент
2. Можливість застосування В«турбо - зсувуВ»
В«Турбо - зрушенняВ» може статися, якщо ми виявимо, що суфікс зразка, який сходиться з текстом, коротше, ніж той, який був запомнен раніше.
Нехай u - запомненний сегмент, а v - cуффікс, який співпав під час поточної спроби, такий що uzv - суфікс x. Тоді av - суфікс x, два символи а і b зустрічаються на відстані p в тексті, та суфікс x довжини | uzv | має період довжини p, а значить не може перекрити обидва появи символів а і b в тексті. Найменший можливий зсув має довжину | u | - | v | (його ми і називаємо В«турбо - зрушеннямВ»).
В
1.5. Пошук підрядків за допомогою кінцевого автомата.
1.5.1. Структура автомата.
За визначенням, кінцевий автомат являє собою п'ятірку М = (Q, q 0 , A,,), де:
Q - кінцеве безліч станів;
q 0 Q - початкове стан;
А Q - кінцеве безліч допускають станів;
- кінцевий вхідний алфавіт;
- функція Q х Q, звана функцією переходів автомата.
Спочатку кінцевий автомат знаходиться в стані q 0 . Потім він по черзі читає символи з вхідного рядка. Перебуваючи в стані q і читаючи символ а, автомат переходить в стан (q, a). Якщо автомат знаходиться в стані q A говорять, що він допускає прочитану частина вхідного рядка. Якщо q А, то прочитана частина рядка відкинута. p> З кінцевим станом М пов'язана функція, звана функцією кінцевого стану, обумовлена ​​наступним чином: є стан, в який прийде автомат (з початкового стану), прочитавши рядок w. Автомат допускає рядок w тоді і тільки тоді, коли А
Для кожного зразка Р можна побудувати кінцевий автомат, який шукає цей зразок в тексті. Першим кроком у побудові автомата, відповідного рядку-зразку Р [1 .. m], є побудова за Р допоміжної суфікс-функциии (як в алгоритмі КМП). Тепер визначимо кінцевий автомат, відповідний зразком Р [1 .. m], наступним чином:
В· Його безліч станів Q = {0,1, ..., m}. Початковий стан q 0 = 0. Єдине допускає стан m;
В· Функція переходів визначена співвідношенням (q - стан, - символ): (q, a) = (P q a). (1)
Пояснимо це співвідношення. Потрібен сконструювати автомат таким чином, щоб при його дії на рядок Т співвідношення
(Т i ) = (Т i )
було інваріантом (тоді рівність (Т i ) = m буде рівносильно тому, що Р входить в Т зі зрушенням i - m, і автомат тим самим знайде всі допустимі зрушення). Однак у цьому випадку обчислення переходу за формулою (1) необхідно для підтримки істинності інваріанту, що випливає з теорем, наведених нижче. [3]
Теорема. Нехай q = (Х), де х - рядок. Тоді для будь-якого символу а має місце (ха) = (P q a). p> Теорема. Нехай - функція кінцевого стану автомата для пошуку підрядка Р [1 .. m]. Якщо Т [1 .. n] - довільний текст, то (Т i ) = (Т i ) для i = 0,1, ..., n. [...
