Міністерство науки і освіти України Національний університет “Львівська політехніка” Інститут комп’ютерних наук та інформаційних технологій кафедра програмного забезпечення Звіт з лабораторної роботи №11 з дисципліни “Алгоритми і структури даних ” Львів 2008 Тема роботи: Ознайомлення із методами пошуку. Алгоритм Кнута-Моріса-Прата. Мета роботи: Вивчити та дослідити методи пошуку, як один із методів обробки даних. Ознайомитись із алгоритмом Кнута-Моріса-Прата. Виконати лабораторну роботу використавши здобуті знання з методів пошуку, зокрема алгоритму Кнута-Моріса-Прата. ТЕОРЕТИЧНІ ВІДОМОСТІ Алгоритм Кнута-Моріса-Прата (англ. Knuth–Morris–Pratt algorithm) шукає входження слова W у рядку S використовуючи просте спостереження, що коли відбувається невідповідність, то слово містить у собі достатньо інформації, для того щоб визначити, де наступне входження може початися, таким чином пропускаючи кілька разову перевірка попередньо порівняних символів. Алгоритм був винайдений вченими Donald Knuth та Vaughan Pratt і незалежно J. H. Morris у 1977 році, але був опублікований у спільній статті. Маємо масив символів S з n елементів (текст) та масив P з m - взірець. Необхідно знайти перше входження взірця в масив. Схема алгоритму полягає у поступовому порівнянні взірця з текстом та зсуву по тексту на кількість співпавших символів у разі знайденого неспівпадіння. Алгоритм КМП КМП1. Встановити і=0. КМП2. j=0, d=1. КМП2. Поки j<m, i<n КМП 3. Перевірка: якщо s[i]=p[j], то d++, i++.j++ поки d != m. Інакше встановити зсув взірця на d позицій по тексту. Перейти на крок КМП2. КМП4. Кінець. Складність алгоритму становить O(n+m). Приклад, Hoola-Hoola girls like Hooligan - текст Hooligan – взірець Hoola-Hoola girls like Hooligan Hooligan i!=a, d=4 Hooligan H!=a, d=1 Hooligan H!=-, d=1 Hooligan i!=a, d=4 ….. Hooligan d=m=8 Текст програми #include<stdio.h> #include<conio.h> #include<iostream.h> #include<string.h> //----------------------------------------------------------------------- int max(int mas[],char t[]) { int i,max=mas[0]; for(i=1; i<signed(strlen(t)); i++) if(mas[i]>max) max=mas[i]; return max; } //----------------------------------------------------------------------- void main() { char s[100],t[10]; int i,j,a,D,d=1,pos; int mas[10]; puts("Vvedit text:"); gets(s); puts("Vvedit ekzemplyar:"); scanf("%s", &t); /*-Заповнення таблиці-*/ for(j=strlen(t)-1; j>=0; j--) { a=0; for(i=j-1;i>=0;i--) if(t[i]==t[j]) { a++; mas[j]=j-i; i=-1; } if(a==0) mas[j]=0; } D=max(mas,t); j=0; while(i<signed(strlen(s))) { if(s[i]==t[j]) { if(j==0) pos=i+1; if(j==signed(strlen(t)-1)) i=strlen(s); i++; j++; d++; } else { if(d>D) d=D; i+=d; j=0; pos=0; } } if(pos==0) puts("Spivpadinnya nemaye!"); else printf("Pershe vhodgennja - %i",pos); getch(); } Протокол роботи програми