Страница 1 из 2
Подстроки в строке
Добавлено: 15 июл 2008, 19:57
Лена89
Привет!
Есть строка: аааа бббб вввв гггг дддд.
Подстроки №1 : аааа бббб;
аааа бббб вввв.
Подстроки №2 : аааа бббб;
аааа бббб вввв;
аааа бббб вввв гггг.
Подстроки №3 : гггг дддд;
аааа ююю ыыыы.
Как программным путем можно определить, какие подстроки, из всех имеющихся, наиболее часто и правильно совпадают со строкой (в данном случае – подстроки №2)? Что бы можно было вывести или записать их куда-нибудь … не суть важно.
Пробовала работать используя - char *strstr( const char *string, const char *strCharSet ); . Но ничего не вышло.
Извините, если вопрос задан непонятно.
Спасибо! Всего наилучшего!
P.S. работаю в Visual C++ 6.0
Re: Подстроки в строке
Добавлено: 15 июл 2008, 20:56
Romeo
Всё верно пыталась, именно эту функцию и следует использовать. Если функция возвращает не NULL, значит подстрока содержится в строке.
Re: Подстроки в строке
Добавлено: 15 июл 2008, 23:10
Vasilisk
А что означает фраза "наиболее часто и правильно совпадают"?
Re: Подстроки в строке
Добавлено: 16 июл 2008, 20:03
Лена89
Т.е. №1 совпадет 2 раза, т.к. они "правильные" (из тех же символов, тоже кол-во символов в слове ...), но их всего 2 (подстроки). №2 совпадет 3 раза, т.к. они "правильные" и их 3, т.е. больше чем 2 в №1. №3 совпадет 1 раз, т.к. одна подстрока "неправильная". Вот и выходит, что №2.
В примере я указала три набора подстрок, но может быть больше. Вопрос как наиболее "по уму", программным путем выявить (исходя из этого примера) подстроки №2.
Возможно опять кривовато написала...извини.
Re: Подстроки в строке
Добавлено: 17 июл 2008, 02:43
Vasilisk
Ну, говорят, что умение ясно излагать есть отражение умения ясно мыслить
Для программиста неумение излагать - системообразующий недостаток.
Насколько я могу понять, в твоих речениях говорится о "жадности" алгоритма - о нахождении вхождения подстроки максимальной длины. В теме "регулярные выражения" этот вопрос всесторонне обсасывается, но у нас C и нет RegEx'a
В таком случае я рекомендую следующий алгоритм. Берётся массив подстрок и упорядочивается так, чтобы самая длинная была первой. Заводится массив счётчиков - той же длины, что число подстрок. Далее организуется цикл, начиная с первого байта строки - перебираются подстроки, начиная сверху и в случае совпадения - приписывается единица в счётчик. Указатель строки сдвигается на один символ и цикл перебора подстрок повторяется...
По окончании алгоритма нужно только проанализировтаь счётчики.
Re: Подстроки в строке
Добавлено: 17 июл 2008, 14:29
Лена89
Спасибо
Vasilisk, что возишься со мной, не смотря на мои системообразующие недостатки!
Понимаю...несколько нагловато с моей стороны просить исходничек, но может сбросищь какой-нибудь на "скорую руку". Я бы доработала.
Re: Подстроки в строке
Добавлено: 18 июл 2008, 04:24
Vasilisk
Лена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 к исходной строке...
Re: Подстроки в строке
Добавлено: 18 июл 2008, 11:06
Лена89
Спасибо! Чмок-чмок!
Re: Подстроки в строке
Добавлено: 18 июл 2008, 11:36
Romeo
" писал(а):Спасибо! Чмок-чмок!
Жуть. Боюсь предположить что было бы, если бы
Vasilisk написал тебе программу целиком
Re: Подстроки в строке
Добавлено: 19 июл 2008, 16:46
Vasilisk
Неа, ничего бы не было. Это был квалифицированно исполненный барышней "развод на понт", с целью выяснить, умеет ли парниша "программировать вааще"
Снимаю шляпу - я вполне доволен состоявшей "серией транзакций".