Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
sonicwave9
0 / 0 / 1
Регистрация: 09.03.2015
Сообщений: 3
#1

Поиск подстроки в строке по алгоритму КМН (Кнута-Морриса-Пратта) - C++

22.10.2015, 20:02. Просмотров 388. Ответов 1
Метки нет (Все метки)

Здравствуйте. Я к вам с вопросом: не могу справиться уже длительное время с лабораторной работой.
Формулировка задания:
Дано слово «микроконтроллер». Проверить можно ли любое введенное пользователем слово, размером меньше предложенного, составить из букв, входящих в заданное слово. Каждую букву можно использовать не больше числа ее вхождений в заданное слово.
Необходимо составить программу, обязательно используя алгоритм Кнута-Морриса-Пратта.
В лабораторной работе была приведена функция с самим алгоритмом:
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
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;
}
Если я правильно понимаю задание, то мне необходимо в саму функцию алгоритма вписать рекурсивную процедуру, которая при несовпадении снова вызывает кмп-алгоритм, но уже считая подстроку с первого несовпадения. Не понимаю, куда и как это вписать.
От отчаяния нашла другой выход: посимвольно искать "подстроку" в нашей предзаданной строке. вышло вот что:
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <iostream>
#include <cstring>
 
using namespace std;
char str[] = "microkontroller";
int KMPSearch(char *string, char *substring){
  int  sl, ssl;
  int res = -1;
  sl = strlen(string);
  ssl = strlen(substring);
  {
    int  i, j = 0, k = -1;
    int  *d;
    d = new int[15];
    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; //Если выполнено условие j == ssl
                                    //то res присваиваем i-ssl иначе присваиваем -1
 
  }
  return res;
}
 
 
int main()
{
 
    char substr[15];
    char substr1[2];
    cout << "wwedite slovo" << endl;
    cin >>substr;
 
int i;
bool flag;
int len = strlen(substr);
    for(i=0; i < len; i++)
    {
        substr1[2]=substr[i];
        cout << substr1[2];
        if (KMPSearch(str, substr1) == -1)
            flag = false;
        else flag = true;
    }
    if (flag == true)
        cout << "mozhno";
    else
        cout <<"nelzya";
}
И оно по неведомым мне, нубу, причинам, не работает.
Очень прошу помощи экспертов: в чем я не права и что мне делать?
Заранее спасибо.
http://www.cyberforum.ru/cpp-beginners/thread1658032.html
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.10.2015, 20:02
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Поиск подстроки в строке по алгоритму КМН (Кнута-Морриса-Пратта) (C++):

Поиск заданной подстроки в строке (алгоритм Кнута-Морриса-Пратта)
Привет всем. Мне нужно написать программу поиска заданной подстроки в строке....

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

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

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

Алгоритм Кнута, Морриса и Пратта
//описание функции алгоритма Кнута, Морриса и Пратта int KMPSearch(char...

1
Dimension
Dimension
573 / 442 / 221
Регистрация: 08.04.2014
Сообщений: 1,709
Завершенные тесты: 1
22.10.2015, 23:29 #2
уверены что кмп обязателен,ибо он для другой задачи предназначен. вашу же легко решить, если завести два массива ,в первом хранить кол-во каждой буквы слова микроконтроллер ,во втором для введенного слова,затем пробежаться по ним и проверить если в первом массиве хватает букв ,то все хорошо.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
22.10.2015, 23:29
Привет! Вот еще темы с решениями:

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

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

Поиск подстроки в строке
Добрый день. Ошибка в программе. Первый раз ищет отлично, потом постоянно...

Поиск подстроки в строке
Найти множество всех слов, которые встречаются в каждом из 2 заданных...


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

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

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