Модераторы: Daevaorn
  

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> поиск вхождения подстроки 
:(
    Опции темы
kleks
Дата 19.1.2006, 00:09 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 40
Регистрация: 6.10.2005

Репутация: нет
Всего: нет
Такой вот вопрос: как можно реализовать поиск первого и следующего вхождения подстроки в строке (не используя стандартных функций для работы со строками):
int pos (char *a, char *b);
int nextpos (char *a, char *b);

Я вот пытался сам сделать..., но получается такая фигня...что даже выкладывать стыдно smile!!!
smile smile заранее благодарен!!!
PM MAIL   Вверх
bel_nikita
Дата 19.1.2006, 00:12 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Эксперт
Сообщений: 2304
Регистрация: 12.10.2003
Где: Поезд №21/22 ( ст . Прага )

Репутация: 21
Всего: 47
memcmp пользуешь?


--------------------
user posted image — регистрация доменов от 150 руб.
PM MAIL WWW ICQ   Вверх
kleks
Дата 19.1.2006, 00:17 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 40
Регистрация: 6.10.2005

Репутация: нет
Всего: нет
Цитата(bel_nikita @ 19.1.2006, 00:12)
memcmp пользуешь?

Если честно, то понятия не имею что это такое smile
PM MAIL   Вверх
bel_nikita
Дата 19.1.2006, 00:27 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Эксперт
Сообщений: 2304
Регистрация: 12.10.2003
Где: Поезд №21/22 ( ст . Прага )

Репутация: 21
Всего: 47
memcmp


--------------------
user posted image — регистрация доменов от 150 руб.
PM MAIL WWW ICQ   Вверх
yaja
Дата 19.1.2006, 00:35 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 98
Регистрация: 30.3.2005
Где: Санкт-Петербург

Репутация: 1
Всего: 1
Вот поиск всех вхождений, остальное легко переделаешь сам smile
Код

const int SIZE = 40;
char T[SIZE], P[SIZE]; // T - сама строка, P - то,что мы ищем в ней
int h[SIZE];

void compute_prefix() {
  int m = strlen(P);
  int k = -1;
  h[0] = k;
  for (int i = 1; i < m; i++) {
    while (k >= 0 && P[k + 1] != P[i]) k = h[k];
    if (P[k + 1] == P[i]) k++;
    h[i] = k;
  }
}

void KMP_search() {
  int n = strlen(T);
  int m = strlen(P);
  compute_prefix();
  int k = -1;
  for (int i = 0; i < n; i++) {
    while (k >= 0 && P[k + 1] != T[i]) k = h[k];
    if (P[k + 1] == T[i]) k++;
    if (k == m - 1) {
      printf("%i\n", i - m + 1); // обнаружили вхождение 
      k = h[k];
    }
  }
}
PM MAIL   Вверх
kleks
Дата 19.1.2006, 00:36 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 40
Регистрация: 6.10.2005

Репутация: нет
Всего: нет
Цитата(yaja @ 19.1.2006, 00:35)
Вот поиск всех вхождений, остальное легко переделаешь сам  smile
Код

const int SIZE = 40;
char T[SIZE], P[SIZE]; // T - сама строка, P - то,что мы ищем в ней
int h[SIZE];

void compute_prefix() {
  int m = strlen(P);
  int k = -1;
  h[0] = k;
  for (int i = 1; i < m; i++) {
    while (k >= 0 && P[k + 1] != P[i]) k = h[k];
    if (P[k + 1] == P[i]) k++;
    h[i] = k;
  }
}

void KMP_search() {
  int n = strlen(T);
  int m = strlen(P);
  compute_prefix();
  int k = -1;
  for (int i = 0; i < n; i++) {
    while (k >= 0 && P[k + 1] != T[i]) k = h[k];
    if (P[k + 1] == T[i]) k++;
    if (k == m - 1) {
      printf("%i\n", i - m + 1); // обнаружили вхождение 
      k = h[k];
    }
  }
}

Конечно спасибо огромное!!!! Но возможно ли это сделать как-нибудь попроще..., т.к. из Вашего кода я практически ничего не понял...заранее благодарен!!!

Это сообщение отредактировал(а) kleks - 19.1.2006, 00:50
PM MAIL   Вверх
_hunter
Дата 19.1.2006, 12:18 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Участник Клуба
Сообщений: 8564
Регистрация: 24.6.2003
Где: Europe::Ukraine:: Kiev

Репутация: 16
Всего: 98
на char*-ах -- вряд ли.
да и нет тут ничего сложного...


--------------------
Tempora mutantur, et nos mutamur in illis...
PM ICQ   Вверх
SergeCpp
Дата 19.1.2006, 12:30 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


 
**


Профиль
Группа: Участник
Сообщений: 955
Регистрация: 8.8.2005
Где: At Home

Репутация: 15
Всего: 124
Точный поиск подстроки в строке

String Algorithmics

Handbook of Exact String Matching Algorithms

Это сообщение отредактировал(а) SergeCpp - 19.1.2006, 12:33


--------------------
http://zoozahita.ru — Бездомные животные Екатеринбурга ищут хозяев
PM MAIL WWW ICQ   Вверх
  
 Ответ в темуСоздание новой темы Создание опроса
Правила форума "С++:Общие вопросы"
Earnest Daevaorn

Добро пожаловать!

  • Черновик стандарта C++ (за октябрь 2005) можно скачать с этого сайта. Прямая ссылка на файл черновика(4.4мб).
  • Черновик стандарта C (за сентябрь 2005) можно скачать с этого сайта. Прямая ссылка на файл черновика (3.4мб).
  • Прежде чем задать вопрос, прочтите это и/или это!
  • Здесь хранится весь мировой запас ссылок на документы, связанные с C++ :)
  • Не брезгуйте пользоваться тегами [code=cpp][/code].
  • Пожалуйста, не просите написать за вас программы в этом разделе - для этого существует "Центр Помощи".
  • C++ FAQ

Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, Earnest Daevaorn
 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | C/C++: Общие вопросы | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.0507 ]   [ Использовано запросов: 22 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.