Подстроки в строке

Модераторы: Romeo, Hawk, Absurd, WinMain, DeeJayC

Лена89
Сообщения: 51
Зарегистрирован: 20 июн 2007, 09:36

Подстроки в строке

Сообщение Лена89 » 15 июл 2008, 18:57

Привет!

Есть строка: аааа бббб вввв гггг дддд.

Подстроки №1 : аааа бббб;
аааа бббб вввв.

Подстроки №2 : аааа бббб;
аааа бббб вввв;
аааа бббб вввв гггг.

Подстроки №3 : гггг дддд;
аааа ююю ыыыы.

Как программным путем можно определить, какие подстроки, из всех имеющихся, наиболее часто и правильно совпадают со строкой (в данном случае – подстроки №2)? Что бы можно было вывести или записать их куда-нибудь … не суть важно.

Пробовала работать используя - char *strstr( const char *string, const char *strCharSet ); . Но ничего не вышло.

Извините, если вопрос задан непонятно.

Спасибо! Всего наилучшего!

P.S. работаю в Visual C++ 6.0

Аватара пользователя
Romeo
Сообщения: 3091
Зарегистрирован: 02 мар 2004, 17:25
Откуда: Крым, Севастополь
Контактная информация:

Re: Подстроки в строке

Сообщение Romeo » 15 июл 2008, 19:56

Всё верно пыталась, именно эту функцию и следует использовать. Если функция возвращает не NULL, значит подстрока содержится в строке.
Entites should not be multiplied beyond necessity @ William Occam
---
Для выделения С++ кода используйте конструкцию [ code=cpp ] Код [ /code ] (без пробелов)
---
Сообщение "Спасибо" малоинформативно. Благодарность правильнее высказать, воспользовавшись кнопкой "Reputation" в виде звёздочки, расположенной в левом нижнем углу рамки сообщения.

Vasilisk
Сообщения: 111
Зарегистрирован: 13 фев 2004, 18:43

Re: Подстроки в строке

Сообщение Vasilisk » 15 июл 2008, 22:10

А что означает фраза "наиболее часто и правильно совпадают"?

Лена89
Сообщения: 51
Зарегистрирован: 20 июн 2007, 09:36

Re: Подстроки в строке

Сообщение Лена89 » 16 июл 2008, 19:03

Т.е. №1 совпадет 2 раза, т.к. они "правильные" (из тех же символов, тоже кол-во символов в слове ...), но их всего 2 (подстроки). №2 совпадет 3 раза, т.к. они "правильные" и их 3, т.е. больше чем 2 в №1. №3 совпадет 1 раз, т.к. одна подстрока "неправильная". Вот и выходит, что №2.
В примере я указала три набора подстрок, но может быть больше. Вопрос как наиболее "по уму", программным путем выявить (исходя из этого примера) подстроки №2.

Возможно опять кривовато написала...извини.

Vasilisk
Сообщения: 111
Зарегистрирован: 13 фев 2004, 18:43

Re: Подстроки в строке

Сообщение Vasilisk » 17 июл 2008, 01:43

Ну, говорят, что умение ясно излагать есть отражение умения ясно мыслить :) Для программиста неумение излагать - системообразующий недостаток.

Насколько я могу понять, в твоих речениях говорится о "жадности" алгоритма - о нахождении вхождения подстроки максимальной длины. В теме "регулярные выражения" этот вопрос всесторонне обсасывается, но у нас C и нет RegEx'a

В таком случае я рекомендую следующий алгоритм. Берётся массив подстрок и упорядочивается так, чтобы самая длинная была первой. Заводится массив счётчиков - той же длины, что число подстрок. Далее организуется цикл, начиная с первого байта строки - перебираются подстроки, начиная сверху и в случае совпадения - приписывается единица в счётчик. Указатель строки сдвигается на один символ и цикл перебора подстрок повторяется...

По окончании алгоритма нужно только проанализировтаь счётчики.

Лена89
Сообщения: 51
Зарегистрирован: 20 июн 2007, 09:36

Re: Подстроки в строке

Сообщение Лена89 » 17 июл 2008, 13:29

Спасибо Vasilisk, что возишься со мной, не смотря на мои системообразующие недостатки! :) Понимаю...несколько нагловато с моей стороны просить исходничек, но может сбросищь какой-нибудь на "скорую руку". Я бы доработала.

Vasilisk
Сообщения: 111
Зарегистрирован: 13 фев 2004, 18:43

Re: Подстроки в строке

Сообщение Vasilisk » 18 июл 2008, 03:24

Лена89 писал(а):Спасибо Vasilisk, что возишься со мной, не смотря на мои системообразующие недостатки! :) Понимаю...несколько нагловато с моей стороны просить исходничек, но может сбросищь какой-нибудь на "скорую руку". Я бы доработала.

Код: Выделить всё


char * stroka; //предполагаем, что это то, что разбираем, она где-то вводится

struct substroka{
  int       n_cnt;    //счётчик вхождений подстрок (при вооде подстроки - обнуляется)
  char * p_ss;      //сама подстрока, она где-то вводится
};

substroka ss[<сколько-то там подстрок>];


//бо-о-ольшой :) главный цикл, в котором мы едем по одному символу вправо и гоним 
//сравнение со всем массивом подстрок, что у нас есть
for(int i=0; i<::strlen(stroka); i++){
  
  for(j=0; j<сколько-то там подстрок; j++){

    if(::strcmp(stroka+1,ss[j].p_ss) == 0) ss[j].n_cnt++;

                                                               }  
}

//здесь надо проанализировать содержимое всех ss[...].n_cnt и принять решение, которая подстрока оказалась the closest к исходной строке...


Лена89
Сообщения: 51
Зарегистрирован: 20 июн 2007, 09:36

Re: Подстроки в строке

Сообщение Лена89 » 18 июл 2008, 10:06

Спасибо! Чмок-чмок!

Аватара пользователя
Romeo
Сообщения: 3091
Зарегистрирован: 02 мар 2004, 17:25
Откуда: Крым, Севастополь
Контактная информация:

Re: Подстроки в строке

Сообщение Romeo » 18 июл 2008, 10:36

&quot писал(а):Спасибо! Чмок-чмок!
Жуть. Боюсь предположить что было бы, если бы Vasilisk написал тебе программу целиком :)
Entites should not be multiplied beyond necessity @ William Occam
---
Для выделения С++ кода используйте конструкцию [ code=cpp ] Код [ /code ] (без пробелов)
---
Сообщение "Спасибо" малоинформативно. Благодарность правильнее высказать, воспользовавшись кнопкой "Reputation" в виде звёздочки, расположенной в левом нижнем углу рамки сообщения.

Vasilisk
Сообщения: 111
Зарегистрирован: 13 фев 2004, 18:43

Re: Подстроки в строке

Сообщение Vasilisk » 19 июл 2008, 15:46

Неа, ничего бы не было. Это был квалифицированно исполненный барышней "развод на понт", с целью выяснить, умеет ли парниша "программировать вааще" :) :) :) Снимаю шляпу - я вполне доволен состоявшей "серией транзакций".

Ответить