+ Ответить в теме
Показано с 1 по 10 из 10

Тема: Подстроки в строке

  1. #1
    programmer Лена89 is on a distinguished road
    Регистрация
    20.06.2007
    Сообщений
    51
    Вес репутации
    12

    По умолчанию Подстроки в строке

    Привет!

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

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

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

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

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

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

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

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

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

  2. По умолчанию

     
    Хотите избавиться от рекламы? Зарегистрируйтесь
  3. #2
    Moderator Куратор
    system architect
    Romeo is on a distinguished road Аватар для Romeo
    Регистрация
    02.03.2004
    Адрес
    Крым, Севастополь
    Возраст
    37
    Сообщений
    3,091
    Вес репутации
    22

    По умолчанию Re: Подстроки в строке

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

  4. #3
    developer Vasilisk is on a distinguished road
    Регистрация
    13.02.2004
    Сообщений
    111
    Вес репутации
    16

    По умолчанию Re: Подстроки в строке

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

  5. #4
    programmer Лена89 is on a distinguished road
    Регистрация
    20.06.2007
    Сообщений
    51
    Вес репутации
    12

    По умолчанию Re: Подстроки в строке

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

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

  6. #5
    developer Vasilisk is on a distinguished road
    Регистрация
    13.02.2004
    Сообщений
    111
    Вес репутации
    16

    По умолчанию Re: Подстроки в строке

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

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

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

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

  7. #6
    programmer Лена89 is on a distinguished road
    Регистрация
    20.06.2007
    Сообщений
    51
    Вес репутации
    12

    По умолчанию Re: Подстроки в строке

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

  8. #7
    developer Vasilisk is on a distinguished road
    Регистрация
    13.02.2004
    Сообщений
    111
    Вес репутации
    16

    По умолчанию Re: Подстроки в строке

    Цитата Сообщение от Лена89 Посмотреть сообщение
    Спасибо Vasilisk, что возишься со мной, не смотря на мои системообразующие недостатки! Понимаю...несколько нагловато с моей стороны просить исходничек, но может сбросищь какой-нибудь на "скорую руку". Я бы доработала.
    Код :
    1.  
    2. char * stroka; //предполагаем, что это то, что разбираем, она где-то вводится
    3.  
    4. struct substroka{
    5.   int       n_cnt;    //счётчик вхождений подстрок (при вооде подстроки - обнуляется)
    6.   char * p_ss;      //сама подстрока, она где-то вводится
    7. };
    8.  
    9. substroka ss[<сколько-то там подстрок>];
    10.  
    11.  
    12. //бо-о-ольшой :) главный цикл, в котором мы едем по одному символу вправо и гоним
    13. //сравнение со всем массивом подстрок, что у нас есть
    14. for(int i=0; i<::strlen(stroka); i++){
    15.  
    16.   for(j=0; j<сколько-то там подстрок; j++){
    17.  
    18.     if(::strcmp(stroka+1,ss[j].p_ss) == 0) ss[j].n_cnt++;
    19.  
    20.                                                                }  
    21. }
    22.  
    23. //здесь надо проанализировать содержимое всех ss[...].n_cnt и принять решение, которая подстрока оказалась the closest к исходной строке...

  9. #8
    programmer Лена89 is on a distinguished road
    Регистрация
    20.06.2007
    Сообщений
    51
    Вес репутации
    12

    По умолчанию Re: Подстроки в строке

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

  10. #9
    Moderator Куратор
    system architect
    Romeo is on a distinguished road Аватар для Romeo
    Регистрация
    02.03.2004
    Адрес
    Крым, Севастополь
    Возраст
    37
    Сообщений
    3,091
    Вес репутации
    22

    По умолчанию Re: Подстроки в строке

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

  11. #10
    developer Vasilisk is on a distinguished road
    Регистрация
    13.02.2004
    Сообщений
    111
    Вес репутации
    16

    По умолчанию Re: Подстроки в строке

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

+ Ответить в теме

Похожие темы

  1. поиск подстроки
    Доброго утра всем Подскажите, кто какими функциями пользуется для поиска подстроки в строке и почему именно этими? Спасибо
    от Dim...ON в разделе C и C++
  2. подстроки
    Даны две строки: S1 и S2. Удалить из строки S1 (S1 – строка выделения) все подстроки, совпадающие с S2. Если таких подстрок нет, то выделение...
    от pikass в разделе MS Office и VB(A).
  3. Командная строка
    Помогите, пожалуйста!!! Мне нужен код программы, которая удаляет файл ,указанный в командной строке. Это выглядит примерно вот так: Указываем путь к...
    от Lex в разделе Ассемблер
  4. Строка наоборот
    здраствуйте! У меня такая задача. Довольно простая, но сколько не думал, не смог додумать: Есть текстовое поле Edit1, из него нужно взять текст и в...
    от senator в разделе Delphi и Pascal
  5. Вставка в текст подстроки в определенное фокусом место?
    Так вот!... Есть TEXTAREA, и кнопка. При нажати на кнопку, в TEXTAREA должен добавиться определенный текст, например "Yahooo!". но не в конец (типа...
    от Zvepr в разделе JScript, VBScript, DHTML...

Ваши права

  • Вы не можете создавать новые темы
  • Вы не можете отвечать в темах
  • Вы не можете прикреплять вложения
  • Вы не можете редактировать свои сообщения