1

Тема: Підпослідовність в послідовності.(КМП)

Користуючись методом Кнута – Моріса – Пратта (КМП) пошуку підпослідовності у послідовності, встановити входження деякого образу у базовий рядок. Якщо співпадання має місце, то вказати порядковий індекс елемента в базі, починаючи з якого образ повністю співпадає з елементами бази, інакше – вивести повідомлення про його відсутність. Визначити кількість важких операцій порівняння, що виконуються при цьому.
a = (1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 2),
b = (1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 1; 2)

2

Re: Підпослідовність в послідовності.(КМП)

program xren;
var
srav,sovpalo:integer;
const a:array[1..18] of integer=(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2);
const b:array[1..15] of integer=(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2);
Procedure Prefix;
Begin
P[1]:=0;
sovpalo:=0;
for j:=1 to 14 do
begin
for var i:=1 to 18-15 do
begin
Prefix;
sovpalo:= 0;
for var j:=1 to 15 do
begin
while (sovpalo>0) and (a[i+j]<>b[j]) do
sovpalo:=P[sovpalo];
if (a[i+j] = b[j]) then sovpalo := sovpalo +1;
srav:= srav + 1;
end;

if (sovpalo = 15) then
begin
writeln(i);
writeln(srav);
end;
end;
end;
end.
Накрутив шось отаке, сам нерозумію шо може хтось підправить ато з цим префіксом зовсім нічього нерозумію.

3

Re: Підпослідовність в послідовності.(КМП)

Просто підкажіть як правельно ввести в програму реалізацію функції для данного методу пошуку, в вікіпедії купа прикладів але саме під мої умови я неможу правельно переробити.

4

Re: Підпослідовність в послідовності.(КМП)

Берете псевдокод з вікіпедії і переписуєте кожен рядок на Паскаль (а сам рядок лишаєте поруч як коментар). Спробуйте.
І вам тут не обов'язково потрібні процедури, можна просто вбити код пошуку допоміжної таблиці на те місце, де він буде використаний на початку програми (тільки не забудьте полічити порівняння в ньому також).

Подякували: pETRUk1

5 Востаннє редагувалося pETRUk (19.11.2014 10:55:04)

Re: Підпослідовність в послідовності.(КМП)

алгоритм таблиця_кмп:
    вхід:
        масив символів, W (слово до розбору)
        масив цілих, T (таблиця до наповнення)
    вихід:
        нічого (але під час дії наповнюється таблиця)

    визначення змінних:
        ціле, pos ← 2 (поточна позиція в T)
        ціле, cnd ← 0 (базований на нулі індекс у W наступного
символу в поточному підрядку кандидаті)

    (перші кілька значень фіксовані, і відрізняються від запропонованих алгоритмом)
    нехай T[0] ← -1, T[1] ← 0

    доки pos менше ніж довжина W, виконувати:
        (перший варіант: підрядок продовжується)
        якщо W[pos - 1] = W[cnd],
          нехай cnd ← cnd + 1, T[pos] ← cnd, pos ← pos + 1

        (другий випадок: не продовжується, але ми можемо відступити)
        інакше, якщо cnd > 0, нехай cnd ← T[cnd]

        (третій випадок: ми вичерпали всіх кандидатів.  Зауважимо cnd = 0)
        інакше, нехай T[pos] ← 0, pos ← pos + 1
ось це переписувать? Тільки в паскаль?

6

Re: Підпослідовність в послідовності.(КМП)

pETRUk
Бачу у вас проблема зі змінними. Прочитайте отут розділ "Переменные": http://www.delphikingdom.com/asp/viewit … alogid=930 А тут можна почитати про процедури та функції: http://www.delphikingdom.com/asp/viewit … logid=1179

7

Re: Підпослідовність в послідовності.(КМП)

Що стосується псевдокоду, то він вимагає гарного знання мови, на якій програмуєш. Приміром оцю частину:

алгоритм пошук_кмп:
    вхід:
        масив символів, S (текст пошуку)
        масив символів, W (шукане слово)
    вихід:
        ціле число (базована на нулі позиція в S, в якій знайдено W)

    визначаємо змінні:
        ціле число, m ← 0 (початок поточного збігу в S)
        ціле число, i ← 0 (позиція поточного символу в W)
        масив цілих чисел, T (таблиця обчислена деінде)
    ...

Можна отак перекласти на паскаль:

var
  T: array[1..100] of integer; {таблиця обчислена деінде}

function Poshuk_KMP(S, W: string): integer;
var
  m, i: integer;
begin
  m := 0;
  i := 0;
  //...
end;

8

Re: Підпослідовність в послідовності.(КМП)

От там, де //..., і треба обчислювати T.
А ввід S,W можна зробити так:

{    вхід:
        масив символів, S (текст пошуку)
        масив символів, W (шукане слово)}
const S:array[1..18] of integer=(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2);
const W:array[1..15] of integer=(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2);

і, ще раз, дуже бажано всюди лишати як коментарі шматки псевдокоду - тоді одразу буде видно, де що робиться.

9

Re: Підпослідовність в послідовності.(КМП)

koala
Щось мені здається, що ви сюди не заходили: http://uk.wikipedia.org/wiki/%D0%90%D0% … 1.96.D0.B2 бо там чітко позначено, де алгоритм пошуку, а де побудова таблиці T.
А що до заміни string на масиви, то з цим я цілком згодний, у нашому випадку звичайно потрібні масиви.