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

подстрока - C++

Восстановить пароль Регистрация
 
Егорка47
7 / 6 / 1
Регистрация: 26.10.2010
Сообщений: 249
22.01.2011, 10:45     подстрока #1
в заданной строке найти позицию первого вхождения указанной подстроки .не используя стандартные функции.спасибо!
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.01.2011, 10:45     подстрока
Посмотрите здесь:

C++ Подстрока
подстрока С++ C++
Завершающая подстрока C++
C++ Наибольшая общая подстрока
Задача: плохая подстрока. Усовершенствовать алгоритм C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
RUSya82
 Аватар для RUSya82
236 / 114 / 3
Регистрация: 15.10.2010
Сообщений: 395
22.01.2011, 10:59     подстрока #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
//-----------Функция поиска подстроки, реализующая алгоритм Бойра-Мура   
int findBM (char A[], int n, char S[], int m)
{
      int i, j, k;
      int r[256]; //Массив сдвигов
      for (k=0;k<256;k++) //заполняем сначала весь массив значениями m
         r[k] = m;
      for (j=0;j<m-1;j++)
      {
         r[(int)(S[j])] = m-j-1;
      }
      i = m;
      j = m;
      //-----начинаем поиск
      do
      {
         j=m;//так как поиск начинается с конца, то
         k=i;
         do
         {
            j--;//нумерация элементов массива начинается с нуля
            k--;
         }while((j>=0) && (A[k] == S[j]));//цикл прерывается, если все символы совпали, или произошел промах
         i = i + r[(int)(A[i-1])];//промах произошел на i-1 элементе, сдвигаемся на соответсвующее количество символов
      }while ((j>=0) && (i <= n));//если j<0, то совпадение найдено, если i>n,то проверили весь массив А
      if (j<0)
         return k+1;
      else  
         return -1;
}
Егорка47
7 / 6 / 1
Регистрация: 26.10.2010
Сообщений: 249
22.01.2011, 11:17  [ТС]     подстрока #3
для чего массив 256?можете написать комментарии ко всей программе более подробно,для очень тупыхбуду должен!
RUSya82
 Аватар для RUSya82
236 / 114 / 3
Регистрация: 15.10.2010
Сообщений: 395
22.01.2011, 11:49     подстрока #4
Это массив сдвигов. Туда мы пишем сдвиг для каждого из 256 символов таблицы ASCII. По моему комментов достаточно. Если хочешь понять, то лучше почитай в чем состоит сам алгоритм - чего я сам не помню толком, так как давно писал. Тут два варианта: либо ты просто почитаешь сам, либо должен читать(вспоминать) я , а потом рассказывать тебе. По моему первый вариант проще.
Егорка47
7 / 6 / 1
Регистрация: 26.10.2010
Сообщений: 249
22.01.2011, 11:53  [ТС]     подстрока #5
я просто с телефоналадно,все равно спасибо огромное!
panicwassano
590 / 558 / 20
Регистрация: 07.11.2010
Сообщений: 2,004
22.01.2011, 14:00     подстрока #6
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
char * GetSubStr(char *sub, char *str)
{
    char *pstr, *psubstr, *start;
    for (int i = 0; str[i]; ++i)
    {
 
        pstr = start = str + i;
        psubstr = sub;
 
        while(*psubstr && *psubstr == *pstr)
        {
            ++pstr;
            ++psubstr;
        }
 
        if (!*psubstr)
        {
            return start;
        }
    }
 
    return NULL;
}
C
1
2
3
4
5
6
char *substr;
substr = GetSubStr("два", "один два три четыре");
if (substr)
{
    cout << "Заданная подстрока: " << substr << endl;
}
Yandex
Объявления
22.01.2011, 14:00     подстрока
Ответ Создать тему
Опции темы

Текущее время: 09:14. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru