Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 18, средняя оценка - 4.89
rostik123456789
0 / 0 / 0
Регистрация: 30.09.2012
Сообщений: 25
#1

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

10.01.2013, 15:42. Просмотров 2855. Ответов 3
Метки нет (Все метки)

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
//описание функции алгоритма Кнута, Морриса и Пратта
int KMPSearch(char *string, char *substring){
  int  sl, ssl;
  int res = -1;
  sl = strlen(string);
  ssl = strlen(substring);
  if ( sl == 0 ) 
    cout << "Неверно задана строка\n"; 
  else if ( ssl == 0 ) 
    cout << "Неверно задана подстрока\n"; 
  else {
    int  i, j = 0, k = -1;
    int  *d;
    d = new int[1000];
    d[0] = -1;
    while ( j < ssl - 1 ) {
      while ( k >= 0 && substring[j] != substring[k] ) 
        k = d[k];
      j++;
      k++;
      if ( substring[j] == substring[k] )
        d[j] = d[k];
      else 
        d[j] = k;
    }
    i = 0;
    j = 0;
    while ( j < ssl && i < sl ){
      while ( j >= 0 && string[i] != substring[j] )
        j = d[j];
      i++;
      j++;
    }
    delete [] d;
    res =  j == ssl ? i - ssl : -1;
  }
  return res;
}
Может кто-то объяснить что и как происходит в этом коде, я почему-то не очень понимаю, но хочу понять, что происходит в коде.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.01.2013, 15:42
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Алгоритм Кнута, Морриса и Пратта (C++):

Алгоритм Кнута-Морриса-Пратта - C++
Здравствуйте. Есть задание в котором необходимо найти вхождения подстроки в строку.Пример входных и выходных данных: 1 2 3 4 2 3 ...

Алгоритм Кнута-Морриса-Пратта - C++
здравствуйте. можете объяснить по примеру алгоритм кнута-морриса-пратта

Алгоритм КМП(Кнута-Морриса-Пратта ) - C++
нужно с помощью алгоритма КМП найти первое вхождение одной числовой последовательности в другую ... не сроки! спасибо

Алгоритм поиска по строке Кнута-Морриса-Пратта - C++
Само задание таково: Программа должна быть грамотно функционально разбита на модули и функции. • Входные данные – текстовый файл. ...

Поиск заданной подстроки в строке (алгоритм Кнута-Морриса-Пратта) - C++
Привет всем. Мне нужно написать программу поиска заданной подстроки в строке. Если подстрока есть - вывести YES. Если нет - NO. Задача...

Быстрый поиск подстроки в строке (Кнута-Морриса-Пратта) - C++
Всем здрасьте. Преподаватель дал задание, найти подстроку в строке. Я задание это выполнил. Он сказал что мой алгоритм будет работать...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
FlaYnoSt
0 / 0 / 0
Регистрация: 10.01.2013
Сообщений: 18
10.01.2013, 16:06 #2
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
int KMPSearch(char *string, char *substring){ //в качестве параметров в функцию передается строка и субстрока
  int  sl, ssl;
  int res = -1;
  sl = strlen(string);                                            //присваивается длина строки
  ssl = strlen(substring);                                      //присваивается длина субстроки
  if ( sl == 0 )                                                    //проверка строки
    cout << "Неверно задана строка\n"; 
  else if ( ssl == 0 )                                            //проверка субстроки
    cout << "Неверно задана подстрока\n"; 
  else {                                                            //Если все нормально - поехали
    int  i, j = 0, k = -1;
    int  *d;
    d = new int[1000];                                         //создали динамический одномерный массив
    d[0] = -1;                                                    //первый элемент делаем равным -1
    while ( j < ssl - 1 ) {                                      //пока  j < кол-ва эл-тов строки
      while ( k >= 0 && substring[j] != substring[k] ) /*пока k больше или равно 0 и j-тый элемент субстроки не равен
                                                                     k-тому присваиваем k k-тый элемент динамического массива*/
        k = d[k];                                                 
      j++;                                                         //увеличиваем j
      k++;
      if ( substring[j] == substring[k] )                   //если j-ый элемент субстроки равен k-тому
        d[j] = d[k];                                             //присваиваем j-тому элементу динамического массива k-тый
      else                                                         //иначе
        d[j] = k;                                                 //присваиваем k
    }
    i = 0;
    j = 0;                                                         //обнулили i, j
    while ( j < ssl && i < sl ){                               //пока j < длины субстроки и i < длины строки
      while ( j >= 0 && string[i] != substring[j] )       // пока j >= 0 и i-ый элемент субстроки не равен j-ому
        j = d[j];                                                  //j присваивается j-ый элемент динамического массива
      i++;
      j++;                                                         //увеличиваем i и j
    }
    
    
    delete [] d;                                                 //удаляем динам. массив                                                
    res =  j == ssl ? i - ssl : -1;                           // результатом будет i-ssl если j = ssl и -1 в противном случае
  }
  return res;
}
0
rostik123456789
0 / 0 / 0
Регистрация: 30.09.2012
Сообщений: 25
10.01.2013, 16:35  [ТС] #3
Возможно я неправильно подал свой ​​вопрос, я хочу понять этот алгоритм но не знаю как правильно задать вопрос чтобы вы мне немножко его объяснили, до этого кода я бы хотел, чтобы вы написали алгоритм его работы (не комментарии к коду) чтобы я понял как он работает , т.е. как работает этот код.
0
FlaYnoSt
0 / 0 / 0
Регистрация: 10.01.2013
Сообщений: 18
10.01.2013, 16:42 #4
http://ru.wikipedia.org/wiki/%D0%90%...82%D1%82%D0%B0
http://algolist.manual.ru/search/esearch/kmp.php
http://www.avhohlov.narod.ru/p2250ru.htm

Мельком глянул, вроде то
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.01.2013, 16:42
Привет! Вот еще темы с ответами:

Поиск подстроки в строке по алгоритму КМН (Кнута-Морриса-Пратта) - C++
Здравствуйте. Я к вам с вопросом: не могу справиться уже длительное время с лабораторной работой. Формулировка задания: Дано слово...

Алгоритм Кнутта-Морриса-Пратта. Как вывести на экран число вхождений? - C++
В интернете нашел алгоритм Кнутта-Морриса-Пратта. Там была предоставлена сама реализация алгоритма. Как вывести на экран число вхождений? ...

Пример из Пратта - C++
Немого модифицированный пример из Пратта. Для переменной snack2 при выводе cout-ом работает четко, при выводе через функцию output выносит...

Нужен алгоритм поиска пути в этом лабиринте (будь то волновой алгоритм или алгоритм правой/левой руки ) - C++
#include &quot;stdafx.h&quot; #include &lt;iostream&gt; #include &lt;conio.h&gt; using namespace std; void lab () { int s1 = 0; int s2 =...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
10.01.2013, 16:42
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru