ПЕРЕЛІК ДИСЦИПЛІН:
  • Адміністративне право
  • Арбітражний процес
  • Архітектура
  • Астрологія
  • Астрономія
  • Банківська справа
  • Безпека життєдіяльності
  • Біографії
  • Біологія
  • Біологія і хімія
  • Ботаніка та сільське гос-во
  • Бухгалтерський облік і аудит
  • Валютні відносини
  • Ветеринарія
  • Військова кафедра
  • Географія
  • Геодезія
  • Геологія
  • Етика
  • Держава і право
  • Цивільне право і процес
  • Діловодство
  • Гроші та кредит
  • Природничі науки
  • Журналістика
  • Екологія
  • Видавнича справа та поліграфія
  • Інвестиції
  • Іноземна мова
  • Інформатика
  • Інформатика, програмування
  • Юрист по наследству
  • Історичні особистості
  • Історія
  • Історія техніки
  • Кибернетика
  • Комунікації і зв'язок
  • Комп'ютерні науки
  • Косметологія
  • Короткий зміст творів
  • Криміналістика
  • Кримінологія
  • Криптология
  • Кулінарія
  • Культура і мистецтво
  • Культурологія
  • Російська література
  • Література і російська мова
  • Логіка
  • Логістика
  • Маркетинг
  • Математика
  • Медицина, здоров'я
  • Медичні науки
  • Міжнародне публічне право
  • Міжнародне приватне право
  • Міжнародні відносини
  • Менеджмент
  • Металургія
  • Москвоведение
  • Мовознавство
  • Музика
  • Муніципальне право
  • Податки, оподаткування
  •  
    Бесплатные рефераты
     

     

     

     

     

     

         
     
    Алгоритм Кнута - Морріса - Пратта
         

     

    Інформатика, програмування

    Алгоритм Кнута - Морріса - Пратта

    Реферат

    Алгоритм Кнута-Моріса-Пратта (КМП) одержує на вхід слово

    X = x [1] x [2] ... x [n]

    і переглядає його зліва направо буква за буквою, заповнюючи при це масив натуральних чисел l [1] ... l [n], де

    l [i] = длина слова l (x [1] ... х [i])

    (функція l визначена в попередньому пункті). Словами: l [i] є довжина найбільшого початку слова x [1] ... x [i], одночасно є його кінцем.

    Яке відношення все це має до пошуку подслова?

    Іншими словами, як використовувати алгоритм КМП для визначення того, чи є слово A подсловом слова B?

    Рішення. Застосуємо алгоритм КМП до слова A # B, де # - спеціальна буква, не зустрічається ні в A, ні в B. Слово A є подсловом слова B тоді і тільки тоді, коли серед чисел в масиві l буде число, яке дорівнює довжині слова A.

    Описати алгоритм заповнення таблиці l [1] ... l [n].

    Рішення. Припустимо, що перший i значень l [1] ... l [i] вже знайдені. Ми читаємо чергову літеру слова (тобто x [i +1]) і повинні обчислити l [i +1].

    Іншими словами, нас цікавлять початку Z слова

    x [1] ... x [i +1,

    що одночасно є його кінцями-з них нам треба брати саме довге. Звідки беруться ці початку? Кожне з них (не рахуючи порожнього) виходить з деякого слова Z 'приписуванням букви x [i +1]. Слово Z ' є початком і

    кінцем слова x [1] ... x [i]. Однак не будь-яке слово, яке є початком і кінцем слова x [1] ... x [i], годиться - треба, щоб за ним слідувала буква x [i +1].

    Отримуємо такий рецепт відшукання слова Z. Розглянемо всі початку слова x [1] ... x [i], що є одночасно його кінцями. З них виберемо підходящі - ті, за якими йде буква x [i +1]. З відповідних виберемо саме довге. Приписавши в його кінець х [i +1], отримаємо шукане слово Z. Тепер пора скористатися зробленими нами приготуваннями і згадати, що всі слова, що є одночасно початками і кінцями даного слова, можна отримати повторними застосуваннями до нього функції l з попереднього розділу.

    Ось що виходить:

    i: = 1; 1 [1]: = 0;

    (таблиця l [1] .. l [i] заповнена правильно)

    while i n do begin

    len: = l [i]

    (len - довжина початку слова x [1] .. x [i], яке є

    його кінцем; дедалі довші початку виявилися

    невідповідними)

    while (x [len +1] х [i +1]) and (len> 0) do begin

    (початок не підходить, застосовуємо до нього функцію l)

    len: = l [len];

    end;

    (знайшли підходяще або переконалися у відсутності)

    if x [len +1] = x [i +1] do begin

    (х [1] .. x [len] - найдовше підходяще початок)

    l [i +1]: = len +1;

    end else begin

    (відповідних немає)

    l [i +1]: = 0;

    end;

    i: = i +1;

    end;

    Довести, що число дій у наведеному тільки що алгоритм не перевершує Cn для деякої константи C.

    Рішення. Це не цілком очевидно: обробка кожної чергової букви може зажадати багатьох ітерацій у внутрішньому циклі. Однак кожна така ітерація зменшує len принаймні на 1, і в цьому випадку l [i +1] виявиться помітно менше l [i]. З іншого боку, при збільшенні i на одиницю величина l [i] може зрости не більше ніж на 1, так що часто і сильно спадати вона не може - інакше спадання не буде скомпенсовано зростанням.

    Більш точно, можна записати нерівність

    l [i +1]

         
     
         
    Реферат Банк
     
    Рефераты
     
    Бесплатные рефераты
     

     

     

     

     

     

     

     
     
     
      Все права защищены. Reff.net.ua - українські реферати ! DMCA.com Protection Status