Форум программистов, компьютерный форум CyberForum.ru

В файле-словаре найти и распечатать слова, которые могут быть полностью составлены из других слов словаря - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 5.00
dubfire
1 / 1 / 0
Регистрация: 22.02.2011
Сообщений: 27
18.04.2011, 23:35     В файле-словаре найти и распечатать слова, которые могут быть полностью составлены из других слов словаря #1
В файле-словаре найти и распечатать слова, которые могут быть
полностью составлены из других слов словаря с помощью
конкатенации, например: “БАЛКОН” = “БАЛ” + “КОН”; “БАРСУК”
= “БАР” + “СУК”.

– Для решения задач не использовать стандартные строковые функции.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.04.2011, 23:35     В файле-словаре найти и распечатать слова, которые могут быть полностью составлены из других слов словаря
Посмотрите здесь:

C++ Распечатать те слова, которые являются обращениями других слов в этом предложении
C++ Строки: Выбрать из слов те, которые могут быть получены из образца по правилу
C++ В файле-словаре найти и распечатать слова, которые могут быть полностью составлены из других слов словаря
подсчитать в заданной строке число слов, которые могут быть разделены пробелом, табуляцией, переводом строки C++
Найти слова которые могут быть полностью сложены из других слов,сцепление слов(конкатенация) C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Aye Aye
 Аватар для Aye Aye
367 / 281 / 36
Регистрация: 17.12.2009
Сообщений: 567
19.04.2011, 04:46     В файле-словаре найти и распечатать слова, которые могут быть полностью составлены из других слов словаря #2
По любому придется перебирать все варианты в тупую.
Пусть слова в файле разделяются произвольным количеством символов '\t' '\n' ' '.
Считываем все слова из фала в массив.
Для каждого слова из массива выбираем каждое слово из того же массива по очереди, производим слияние слов, получим одно новое слово, теперь просто ищем его среди элементов того же массива.
Насчет стандартных строковых функций: самому придется написать некоторый эквивалент, всего то strcpy, strcmp и все, пожалуй.

Добавлено через 22 минуты
у этого алгоритма сложность O(n^3), но он очень простой.
можно составить алгоритм со сложностью O(k*n^2), где k число слов, начинающихся с одного из других слов словаря.
Для каждого слова найти индексы всех слов начинающихся с него, затем для каждого слова проверить не заканчиваются ли на него слова с найденными индексами.
dubfire
1 / 1 / 0
Регистрация: 22.02.2011
Сообщений: 27
19.04.2011, 15:42  [ТС]     В файле-словаре найти и распечатать слова, которые могут быть полностью составлены из других слов словаря #3
Цитата Сообщение от Aye Aye Посмотреть сообщение
Для каждого слова из массива выбираем каждое слово из того же массива по очереди, производим слияние слов, получим одно новое слово, теперь просто ищем его среди элементов того же массива.
Насчет стандартных строковых функций: самому придется написать некоторый эквивалент, всего то strcpy, strcmp и все, пожалуй.
Наверное проше будет тупо перебрать), можеш плиз кодом описать как слово искать (как ты выше писал), и вот с функциями я что-то тож не очень понял?)
Aye Aye
 Аватар для Aye Aye
367 / 281 / 36
Регистрация: 17.12.2009
Сообщений: 567
20.04.2011, 16:13     В файле-словаре найти и распечатать слова, которые могут быть полностью составлены из других слов словаря #4
Ну что-то вроде этого:
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
int main()
{
  // сначала отрываем файл file
  // и читаем данные в массив
  char *dict[100];
  int i = 0;
  while (!feof(file)) {
    char buf[64];
    fscanf(file, "%s", buf);
    dict[i] = malloc(strilen(buf) + 1);
    strcpy(dict[i], buf);
   ++i;
  }
  int n = i; // n количество элементов в массиве
 
  // ну и тут уже ищем в массиве чего так да как.
  for (i = 0; i < n;) {
    char buf[32];
    bzero(buf, 32); // забить нулями
    strcat(buf, dict[i]);
    int j;
    for (j = 0; j < n) {
      strcat(buf, dict[j]);
      int k;
      // на этом этапе имеем в buf результат конкатинации двух строк
      for (k = 0; k < n; ++k) {
         if (strcmp(dict[k], buf) == 0) { // если одно из слов совпало с результатом конкатинации
           printf("%s\n", dict[k]);
         }
      }
      // освободим буфер от второго слова в нем.
      k = strlen(dict[j]);
      bzero(&buf[k + 1], 32 - k - 1);
    }
  }
 
  // в конце программы надо освободить память.
  for (i = 0; i < n; ++i) {
    free(dict[i]);
  }
  return 0;
}
а насчет функций, тебе же, все равно, придется делать побуквенное сравнение строк и все такое. Для этого лучше написать функции, чем прямо так в код вставить. Раз по заданию нельзя использовать стандартные пиши свои.

П.С. не компилировал.
Yandex
Объявления
20.04.2011, 16:13     В файле-словаре найти и распечатать слова, которые могут быть полностью составлены из других слов словаря
Ответ Создать тему
Опции темы

Текущее время: 07:01. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru