Нужна помощь со строками на C++

[SBerT]

Задача: Найти в строке самое маленькое по количеству слов множество, в словах которого содержатся все буквы алфавита.

Создавать строку и вычленять слова в кучу, создавая динамический массив указателей на них, умею. Может ли кто-нибудь подсказать сам алгоритм решения задачи?

[SBerT]

По идее тут должен быть стандартизированный алгоритм? Я пытаюсь найти его в разных источниках, но пока безрезультатно. Может кто-то уже сталкивался?

[SBerT]

Пожалуйста, откликнитесь, кто знает. Очень нужно к среде.

[ROD]

Если множество моджет состоять толко из подрядидущих слов, то я бы сначало сделал бы масив запосненный номерами ячеек, содежащих первую букву каждого слова. Затем я бы сделал бы масив состоящий из 23 элементов (если я не ошибаюсь. тов английском языке именно столько букв).

Далее цикл
for (i=a[x]; x < n; x++) //Где a[х] это элемент масива содержащего первый символ текущего слова (точнее номер его ячейки).
for (j=i;j<n;j++)
{

switch(text[i])
{case 'a'
{alfavit[0] =1; break}
case 'b'
{alfavit[1] =1; break}

case 'c'
{alfavit[2] =1; break}// и так далее...
}

for (z=0; z<23; z++)
{if (alfavit[z]!= -)
{buki ++;}
}


}

Хм.. кажется я чего-то пропустил... надо еще подумать.

[pu4koff]

Как вариант посмотреть в сторону теории множеств. В С++ правда я не помню есть ли они вообще и если есть, то в каком виде, но идея в следующем:
- Вырезаем из строки первое слово
- Пробегаем по нему и заполняем множество имеющихся в нём букв
- Добавляем в список (или в чём там будете хранить) слов
- Вырезаем второе слово
- Определяем для него множество букв
- проверяем, есть ли у нас уже слово, которое имеет такое же или большее множество букв (т.е. кажется так по теории будет: Б - А = (пустое множество), шде Б - множество для второго слова, А - для первого). если есть, то не добавлять слово в общее хранилище, т.к. есть уже более подходящий аналог. Если же наоборот уже есть "худшее" слово, т.е. (А - Б = () и Б - А != ()), то удаляем из списка то слово и заносим новое.
// Пробегаем так по всем словам

Поиск оптимального множества слов примерно такой будет:
берём множество, в котором заполнены все буквы и проверяем все комбинации слов. из этого полного множества вычитаем множество конкретного слова. В итоге такими вычитаниями нужно получить пустое множество. Но тут сложность алгоритма растет по экспоненте наверно и на 10 словах "весело" будет.